Problem
Padang rumput Farmer John boleh dianggap sebagai
NxN grid (
\(1<=N<=500\)) sel segi empat sama dengan rumput (seperti papan Catur yang besar). Disebabkan oleh kebolehubahan tanah, rumput dalam beberapa sel lebih hijau daripada yang lain. Setiap sel
(i,j) diterangkan oleh integer - tahap kehijauan
G(i,j), dalam selang
\ (1…200\).
Petani John mahu mengambil gambar sub-grid segi empat tepat di padang rumputnya. Dia mahukan minimum G dalam fotonya menjadi tajam 100. Bantu dia mengira berapa banyak gambar berbeza yang boleh diambilnya. Subgrid boleh berkisar dalam saiz dari keseluruhan padang rumput hingga satu sel. Terdapat \(N^2(N+1)^2/4\) sublattices yang berbeza, gunakan integer 64-bit (seperti < code>long panjang dalam C++).
Input
Baris pertama mengandungi
N. Setiap satu daripada
N garisan berikut mengandungi N integer dan bersama-sama ia menerangkan magnitud G(i,j) ; ;untuk padang rumput NхN .
Cetakan
Keluarkan bilangan gambar berbeza yang boleh diambil oleh Farmer John, i.e. bilangan sublattices segi empat tepat di mana tahap minimum "kehijauan" tepat 100.
Perhatikan bahawa jawapan memerlukan pembolehubah integer 64-bit jenis long long dalam C++.
Contoh
| # |
Input |
Output |
| 1 |
3
57 120 87
200 100 150
2 141 135
| 8 |