Задача
Пастбище Фермера Джона может рассматриваться как
NхN решётка (
\(1<=N<=500\)) квадратных ячеек с травой (как большая шахматная доска). Из-за изменчивости почвы, трава в некоторых ячейках зеленее, чем в других. Каждая ячейка
(i,j) описывается целым числом - уровнем зелёности
G(i,j), в интервале
\(1…200\).
Фермер Джон хочет сделать фотографию прямоугольной подрешётки своего пастбища. Он хочет, чтобы минимальная из величин G на его фотографии была ровна 100. Помогите ему посчитать, сколько таких различных фотографий он сможет сделать. Подрешётка может быть размером от всего пастбища и до одной ячейки. Всего существует \(N^2(N+1)^2/4\) различных подрешёток, для хранения такого числа используйте 64-битное целое (типа long long в C++).
Входные данные
Первая строка содержит
N. Каждая из следующих
N строк содержит
N целых чисел и все вместе они описывают величины
G(i,j) для пастбища
NхN .
Выходные данные
Выведите количество различных фотографий, которые может сделать Фермер Джон, т.е. количество прямоугольных подрешёток, в которых минимальный уровень "зелёности" ровно
100.
Заметим, что для ответа требуется использовать 64-битную целую переменную типа long long в C++.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
57 120 87
200 100 150
2 141 135 |
8 |