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