Problem
Cat Goose, Nick Fury için 0<'tan sayıları içeren \(n \cdot m\) boyutunda dikdörtgen bir a tablosu hazırladı /span> code> ile p−1 arasında. Nick Fury, bu tablodaki her sayının 0 ile p− arasında eşit olasılıkla rastgele seçildiğini hemen fark etti. 1 , diğerlerinden bağımsız olarak.
Göreviniz — bu tablonun, toplamın p ile bölünebildiği dikdörtgen bir alt matrisini bulun. Bütün bu tür alt matrisler arasında, öğelerin toplamının maksimum olduğu matrisi bulmanız gerekir.
Resmi olarak,
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\), tüm
\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\) p üzerinde bölünmüştür ve bunlar arasında maksimum miktara sahiptir.
Giriş
İlk satır üç tamsayı içerir n, m, p (\(1 < ;= n m, p <= 1.000.000\)) — matrisin boyutları ve alt matrisin toplamının bölünmesi gereken sayı.
Aşağıdaki n satırları, m tamsayılarını, i'inci satırdaki j'inci sayıyı içerir eşittir ai,j (\(0 <= a_{i,j} <= p ? 1\) ).
a içindeki her bir sayının, bağımsız olarak rastgele, eşit olasılıkla 0 ile p−1 arasında seçilmesi garanti edilir.
Çıktı
Tek bir tamsayı yazdır — toplamın p ile bölünebildiği bir dikdörtgen alt matrisin maksimum toplamı. Hiçbiri yoksa, 0 yazdırın.
Örnekler
| # |
Girdi |
Çıktı |
| 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 |