会津大å¦ä»˜å±žå¹¼ç¨šåœ’ã¯ãƒ—ãƒã‚°ãƒ©ãƒŸãƒ³ã‚°ãŒå¤§å¥½ããªåä¾›ãŒé›†ã¾ã‚‹å¹¼ç¨šåœ’ã§ã‚る。園å…ã®ä¸€äººã§ã‚るゆã†å›ã¯ã€ãƒ—ãƒã‚°ãƒ©ãƒŸãƒ³ã‚°ã¨åŒã˜ãらã„長方形ãŒå¤§å¥½ãã 。ãã‚“ãªã‚†ã†å›ã¯ï¼“ã¤ã®é•·æ–¹å½¢ã‚’使ã£ã¦å¾—点を得る新ãŸãªéŠã³ã‚’考ãˆã€å¾—られる最大ã®å¾—点を計算ã™ã‚‹ãŸã‚ã®ãƒ—ãƒã‚°ãƒ©ãƒ を書ãã“ã¨ã«ã—ãŸã€‚
H × W マスã®é•·æ–¹å½¢ A , B ã¨h × w マスã®é•·æ–¹å½¢ C ãŒä¸Žãˆã‚‰ã‚Œã‚‹ã€‚ ( H, Wã¯ãã‚Œãžã‚Œé•·æ–¹å½¢A, Bã®ç¸¦, 横ã®ãƒžã‚¹ã®æ•°ã‚’, h, wã¯ãã‚Œãžã‚Œé•·æ–¹å½¢Cã®ç¸¦, 横ã®ãƒžã‚¹ã®æ•°ã‚’表㙠)
図1ã®ã‚ˆã†ã« A ã®å„マスã«ã¯æ•´æ•°ãŒæ›¸ã‹ã‚Œã¦ãŠã‚Šã€Bã®å„マスã«ã¯ç™½ã¾ãŸã¯é»’ã®è‰²ãŒã¤ã„ã¦ã„る。 Cã®å„マスã«ã‚‚åŒæ§˜ã«ç™½ã¾ãŸã¯é»’ã®è‰²ãŒã¤ã„ã¦ã„る。
B ã®ä¸ã« C ã¨å…¨ãåŒã˜æ¨¡æ§˜ã®é•·æ–¹å½¢ãŒã‚ã£ãŸå ´åˆã€A ã®ä¸ã§ãã®é•·æ–¹å½¢å†…ã«å¯¾å¿œã™ã‚‹ãƒžã‚¹ã«æ›¸ã‹ã‚Œã¦ã„ã‚‹æ•´æ•°ã®å’ŒãŒå¾—点ã¨ã—ã¦æ‰‹ã«å…¥ã‚‹ã€‚
例ãˆã°å›³ï¼‘ã®ã‚ˆã†ãªé•·æ–¹å½¢ A, B, C を使ã†å ´åˆã€å›³ï¼’ã®èµ¤ç·šã§ç¤ºã™ã‚ˆã†ã« B ã®ä¸ã« C ã¨åŒã˜æ¨¡æ§˜ãŒå«ã¾ã‚Œã¦ã„ã‚‹ã®ã§ã€ãã®å ´æ‰€ã‹ã‚‰193点ãŒå¾—られる。
B ã®ä¸ã« C ã¨å…¨ãåŒã˜æ¨¡æ§˜ã®é•·æ–¹å½¢ãŒï¼‘ã¤ä»¥ä¸Šå˜åœ¨ã™ã‚‹å ´åˆã€ãã®ã‚ˆã†ãªé•·æ–¹å½¢ã®ä¸ã§æœ€å¤§ä½•ç‚¹ã‚’å¾—ã‚‹ã“ã¨ãŒã§ãã‚‹ã ã‚ã†ã‹ï¼Ÿ
ãŸã ã—ã€B ã®ä¸ã« C ã¨åŒã˜æ¨¡æ§˜ã®é•·æ–¹å½¢ãŒå˜åœ¨ã—ãªã„å ´åˆã¯"NA†( “ ã¯é™¤ã ) ã¨å‡ºåŠ›ã™ã‚‹ã“ã¨ã€‚ ã¾ãŸã€é•·æ–¹å½¢ã‚’回転ã—ãŸã‚Šå転ã™ã‚‹ã“ã¨ã¯ã§ããªã„。
入力ã®å½¢å¼ã¯ä»¥ä¸‹ã®é€šã‚Šã§ã‚る。
H W a(1,1) a(1,2) ... a(1,W) a(2,1) a(2,2) ... a(2,W) : a(H,1) a(H,2) ... a(H,W) b(1,1) b(1,2) ... b(1,W) b(2,1) b(2,2) ... b(2,W) : b(H,1) b(H,2) ... b(H,W) h w c(1,1) c(1,2) ... c(1,w) c(2,1) c(2,2) ... c(2,w) : c(h,1) c(h,2) ... c(h,w)
a(i,j) ã¯é•·æ–¹å½¢ A ã®ãƒžã‚¹ (i, j) ã«æ›¸ã‹ã‚Œã¦ã„ã‚‹æ•´æ•°ã‚’ã€b(i,j)ã¯é•·æ–¹å½¢ B ã®ãƒžã‚¹(i,j)ã®è‰²ã‚’ã€c(i,j) ã¯é•·æ–¹å½¢ C ã®ãƒžã‚¹(i,j)ã®è‰²ã‚’表ã™ã€‚ マスã®è‰²ã¯0 ãŒç™½ã€ï¼‘ ãŒé»’を表ã™ã€‚
入力ã¯ä»¥ä¸‹ã®æ¡ä»¶ã‚’満ãŸã™ã€‚
長方形Bã®ä¸ã«é•·æ–¹å½¢Cã¨å…¨ãåŒã˜æ¨¡æ§˜ã®å ´æ‰€ãŒå˜åœ¨ã™ã‚‹å ´åˆã€ãã®ã‚ˆã†ãªå ´æ‰€ã®ä¸ã§ã‚‚ã£ã¨ã‚‚得点ãŒé«˜ã„ã‚‚ã®ã‚’出力ã›ã‚ˆã€‚
ãã®ã‚ˆã†ãªå ´æ‰€ãŒå˜åœ¨ã—ãªã„å ´åˆ, “NA†( “ ã¯é™¤ã ) ã¨å‡ºåŠ›ã›ã‚ˆã€‚
4 4 10 2 -1 6 8 1 -100 41 22 47 32 11 -41 99 12 -8 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 2 3 1 0 1 0 1 0
193
3 3 5 1 3 2 5 9 0 1 5 1 0 0 0 1 1 0 1 1 1 1 1
9
3 4 4 1 9 1 9 1 -1 3 2 -4 1 10 1 1 0 1 0 1 1 1 1 1 0 0 1 4 1 1 1 1
NA