Problem
キャットグースはニック・フューリーのために、0< からの数字を含むサイズ \(n \cdot m\) の長方形のテーブルを用意しました。 /span> code> から p−1 まで。ニック フューリーは、このテーブルの各数値が 0 から p− まで等しい確率でランダムに選択されたことにすぐに気づきました。 1 、他のものには関係ありません。
あなたのタスク -このテーブルの、合計が p で割り切れる長方形の部分行列を見つけます。 そのようなすべての部分行列の中で、要素の合計が最大になる部分行列を見つける必要があります。
正式には、
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\) は、
\(i_1 <= x <= i_2\)、
\(j_1 <= y <= j_2\) p で分割され、その中で最大量があります。
入力
最初の行には、3 つの整数 n、m、p (\(1 <) が含まれています。 ;= n m, p <= 1,000,000\)) —行列の次元と部分行列の合計を割る数値。
次の n 行には m 個の整数が含まれており、i 行目の j 番目の数値です。 ai,j と等しい (\(0 <= a_{i,j} <= p ? 1\) ).
a 内の各数値は、おそらく 0 から p−1 まで、独立してランダムに選択されることが保証されます。
出力
単一の整数を表示 —合計が p で割り切れる長方形部分行列の最大合計。何もない場合は、0 を出力します。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
6 7 5
0 0 3 0 1 0 4
0 2 3 0 2 2 1
2 4 1 4 4 0 3
1 1 0 2 0 3 2
3 0 3 1 0 1 2
1 2 0 0 3 3 1
|
65 |