AT_agc066_a [AGC066A] Adjacent Difference

[problemUrl]: https://atcoder.jp/contests/agc066/tasks/agc066_a $ N $ 行 $ N $ 列のマス目があります．上から $ i $ 行目，左から $ j $ 列目のマスをマス $ (i,j) $ と表します． 各マスには整数がひとつずつ書き込まれており，はじめマス $ (i,j) $ に書き込まれている整数は $ A_{i,j} $ です． あなたは次の操作を繰り返し行うことができます： - $ 1\leq\ i,\ j\leq\ N $ を満たす整数 $ i,j $ および整数 $ x $ を選び，$ A_{i,j} $ に $ x $ を加える．この操作にはコストが $ |x| $ かかる． 正整数 $ d $ が与えられます．あなたの目標は次の条件が成り立つようにすることです： - 上下左右の $ 4 $ 方向に隣接する $ 2 $ マスに書き込まれている整数の差は $ d $ 以上である．より形式的には，次の $ 2 $ 条件が成り立つ： - $ 1\leq\ i\leq\ N-1 $, $ 1\leq\ j\leq\ N $ を満たす整数 $ i,\ j $ に対して $ |A_{i,j}-A_{i+1,j}|\geq\ d $． - $ 1\leq\ i\leq\ N $, $ 1\leq\ j\leq\ N-1 $ を満たす整数 $ i,\ j $ に対して $ |A_{i,j}-A_{i,j+1}|\geq\ d $． この目標を，総コスト $ \frac12\ dN^2 $ 以下で達成してください．

N/A

N/A

### 制約 - $ 2\leq\ N\leq\ 500 $ - $ 1\leq\ d\leq\ 1000 $ - $ -1000\leq\ A_{i,j}\leq\ 1000 $ ### Sample Explanation 1 次のように $ 4 $ 回の操作を行うと，マス目の状態が出力例の通りになります． - $ (i,j,x)=(1,2,7) $ として操作を行う． - $ (i,j,x)=(2,2,-5) $ として操作を行う． - $ (i,j,x)=(3,1,-2) $ として操作を行う． - $ (i,j,x)=(3,2,7) $ として操作を行う． コストの総和は $ 7+5+2+7=21 $ であり，これは $ \frac{1}{2}dN^2=\frac{45}{2} $ 以下です．