题目描述

Farmer John 的草地可以被看作是一个由 $N \times N$ 个正方形方格（$1 \leq N \leq 500$）组成的方阵（想象一个巨大的棋盘）。由于土壤变异性，某些方格中的草可能更绿。每个方格 $(i,j)$ 可以用一个整数绿度值 $G(i,j)$ 来描述，范围为 $1 \ldots 200$。

Farmer John 想要给他的草地的一个子矩阵拍摄一张照片。他希望确保这一子矩阵看上去足够绿，但又不绿得过分，所以他决定拍摄一个 $G$ 的最小值恰好等于 100 的子矩阵。请帮助他求出他可以拍摄多少不同的照片。子矩阵最大可以为整个草地，最小可以仅为一个方格（共有 $N^2(N+1)^2/4$ 个不同的子矩阵——注意该数可能无法用 $32$ 位整数型存储，所以你可能需要使用 $64$ 位整数类型，例如 C++ 中的 long long）。

输入格式

输入的第一行包含 $N$。以下 $N$ 行每行包含 $N$ 个整数，表示 $N \times N$ 草地的 $G(i,j)$ 值。

输出格式

输出 Farmer John 可以拍摄的不同的照片数量——也就是说，最小绿度值等于 $100$ 的子矩阵数量。

注意这个问题涉及到的整数大小可能需要使用 $64$ 位整数型存储（例如，C/C++ 中的 long long）。

3
57 120 87
200 100 150
2 141 135

8

提示

测试点性质：

• 对于 $50\%$ 的数据，满足 $N\le 200$。
• 对于另外 $50\%$ 的数据，没有额外限制。

供题：Brian Dean