AT_abc347_f [ABC347F] Non-overlapping Squares

[problemUrl]: https://atcoder.jp/contests/abc347/tasks/abc347_f $ N\times\ N $ のマス目があり、上から $ i $ 行目、左から $ j $ 列目 $ (1\leq\ i,j\leq\ N) $ のマスには整数 $ A\ _\ {i,j} $ が書かれています。 整数 $ M $ が与えられます。 $ M\times\ M $ のマス目を重ならないように $ 3 $ つ選ぶときの、選んだマス目に書かれている整数の総和としてありえる最大値を求めてください。 問題の厳密な定義 整数の $ 6 $ つ組 $ (i\ _\ 1,j\ _\ 1,i\ _\ 2,j\ _\ 2,i\ _\ 3,j\ _\ 3) $ が次の $ 3 $ つの条件を満たしているとき、**良い $ 6 $ つ組**ということにします。 - $ 1\leq\ i\ _\ k\leq\ N-M+1\ (k=1,2,3) $ - $ 1\leq\ j\ _\ k\leq\ N-M+1\ (k=1,2,3) $ - $ k\neq\ l\ (k,l\in\lbrace1,2,3\rbrace) $ ならば、$ \lbrace(i,j)\mid\ i\ _\ k\leq\ i\lt\ i\ _\ k+M\wedge\ j\ _\ k\leq\ j\lt\ j\ _\ k+M\rbrace $ と $ \lbrace(i,j)\mid\ i\ _\ l\leq\ i\lt\ i\ _\ l+M\wedge\ j\ _\ l\leq\ j\lt\ j\ _\ l+M\rbrace $ に共通部分はない 良い $ 6 $ つ組 $ (i\ _\ 1,j\ _\ 1,i\ _\ 2,j\ _\ 2,i\ _\ 3,j\ _\ 3) $ に対する値 $ \displaystyle\ \sum\ _\ {k=1}\ ^\ 3\sum\ _\ {i=i\ _\ k}\ ^\ {i\ _\ k+M-1}\sum\ _\ {j=j\ _\ k}\ ^\ {j\ _\ k+M-1}A\ _\ {i,j} $ の最大値を求めてください。 この問題の制約のもとで良い $ 6 $ つ組が存在することが示せます。

N/A

N/A

### 制約 - $ 2\leq\ N\leq\ 1000 $ - $ 1\leq\ M\leq\ N/2 $ - $ 0\leq\ A\ _\ {i,j}\leq10\ ^\ 9 $ - 入力はすべて整数 ### Sample Explanation 1 与えられたグリッドから、以下の図のように $ 3\times3 $ のマス目を $ 3 $ つ選ぶと（これは $ (i\ _\ 1,j\ _\ 1,i\ _\ 2,j\ _\ 2,i\ _\ 3,j\ _\ 3)=(1,5,2,1,5,2) $ とすることに対応します）、選んだマス目に書かれている数の合計は $ 154 $ となります。  問題文の条件を満たす選び方であって選んだマス目に書かれている数の合計が $ 155 $ 以上であるものは存在しないため、$ 154 $ を出力してください。 ### Sample Explanation 2 以下のように選ぶのが最適です。  ### Sample Explanation 3 以下のように選ぶのが最適です。