Олимпиадный тренинг

Задача . Достаточно зеленого


Пастбище Фермера Джона может рассматриваться как 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



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Java1
С++ Mingw-w642
Комментарий учителя