/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
伊織ちゃんのマイブームはピラミッドである。
伊織ちゃんは球状の石を使ったピラミッドに飽きてしまったため、今度は 1 辺の長さが 1 である立方体状の石を使ってピラミッドを作ることにした。伊織ちゃんは以下のような手順でピラミッドを作ることにした。
- N \times N のマス目を紙に書く。各マスの 1 辺の長さは 1 である。i (1 ≦ i ≦ N) 行目 j (1 ≦ j ≦ N) 列目のマスをマス (i,j) と呼ぶことにする。
- 各マスに石を 1 個以上縦に積んで置く。マス (i,j) には H_{i,j} 個の石を積み上げる。
- マスを 1 つ選ぶ。このマスをマス P と呼ぶことにする。
- いくつかの石（0 個でもよい）を取り除く。このとき、残った石が マス P を中心としたピラミッド を構成していなければならない。
ただし、石がマス P を中心としたピラミッドを構成している状態とは以下のような状態である。
-
マス P をマス (Pi,Pj)、マス (i,j) に積まれている石の個数を S_{i,j}、S_{Pi,Pj} を T と呼ぶことにすると、全ての i (1 ≦ i ≦ N), j (1 ≦ j ≦ N) に対して、以下の式が成り立っている。ただし、Abs(x) は x の絶対値を表すものとする。
- S_{i,j} = Max(0, T - Max(Abs(Pi - i), Abs(Pj - j)))
- S_{i,j} ≦ Min(Pi, Pj, N - Pi + 1, N - Pj + 1)
このとき、マス P に積まれている石の個数を ピラミッドの高さ と呼ぶことにする。
全ての i (1 ≦ i ≦ N), j (1 ≦ j ≦ N) に対して、マス (i,j) を中心としたピラミッドを作るときにできるピラミッドの高さの最大値を求め、それらの和を答えよ。
入力
入力は複数のテストケースからなる。
（ テストケースの生成方法が少し特殊ですが、これは入力ファイルのサイズを削減するための措置であり、他に特に深い意味はありません。 ）
入力は以下の形式で標準入力から与えられる。
N Q
X A B C
H_{1,1} H_{1,2} ... H_{1,N}
H_{2,1} H_{2,2} ... H_{2,N}
:
H_{N,1} H_{N,2} ... H_{N,N}
- 1 行目には、マス目の 1 辺の個数を表す整数 N (1 ≦ N ≦ 500) と、テストケース数を表す整数 Q (1 ≦ Q ≦ 10) が空白区切りで与えられる。
- 2 行目には、4 つの整数 X (0 ≦ X < C), A (0 ≦ A < C), B (0 ≦ B < C), C (N ≦ C ≦ 30,000) が空白区切りで与えられる。これらは、テストケースを生成する際の乱数を生成するために使われる整数である。
- 3 行目からの N 行には、最初に各マスに積む石の個数の情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には、N 個の整数が空白区切りで与えられる。このうち j (1 ≦ j ≦ N) 個目の整数 H_{i,j} (1 ≦ H_{i,j} ≦ N) はマス (i,j) に積む石の個数を表す。
出力
出力は Q 行からなる。このうち i 行目には、i 個目のテストケースに対する答えを出力せよ。出力の末尾にも改行を入れること。
ソースコードは以下のようなC言語風の疑似コードに沿って書けばよい。
int N, Q, X, A, B, C;
int H[500][500];
int Rand() {
return X = (A * X + B) % C;
}
void Shuffle() {
for (int i = 0; i < N*N; ++i) {
int ai = Rand() % N;
int aj = Rand() % N;
int bi = Rand() % N;
int bj = Rand() % N;
if (ai == bi && aj == bj) continue;
swap(H[ai][aj], H[bi][bj]);
}
}
void main() {
入力を読み込む
for (int i = 0; i < Q; i++) {
この時点でのN,Hに対する答えを計算し、出力
if (i != Q-1) Shuffle();
}
return 0;
}
入力例1
5 3 0 7 3 101 1 1 1 1 1 1 2 2 2 1 1 2 3 2 1 1 2 2 2 1 1 1 1 1 1
出力例1
35 27 30
1 つ目のテストケースは以下のようになる。
1 1 1 1 1 1 2 2 2 1 1 2 3 2 1 1 2 2 2 1 1 1 1 1 1
このとき、各マスを中心としたピラミッドの高さの最大値は以下のようになる。
1 1 1 1 1 1 2 2 2 1 1 2 3 2 1 1 2 2 2 1 1 1 1 1 1
これらの和は 35 であるため、出力の 1 行目には 35 と出力する。
2 つ目のテストケースは以下のようになる。
2 1 2 1 1 2 1 1 1 1 1 2 1 1 1 2 2 1 1 1 1 2 1 3 2
このとき、各マスを中心としたピラミッドの高さの最大値は以下のようになる。
1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1 1 1 1
これらの和は 27 であるため、出力の 2 行目には 27 と出力する。
3 つ目のテストケースは以下のようになる。
1 1 1 2 1 2 1 1 2 1 1 1 3 1 1 1 2 2 2 2 2 1 1 1 1
このとき、各マスを中心としたピラミッドの高さの最大値は以下のようになる。
1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 2 2 2 1 1 1 1 1 1
これらの和は 30 であるため、出力の 3 行目には 30 と出力する。