Just Green Enough

题目描述

农夫约翰的牧场可以视为一个 $N \times N$ 的网格（$1 \leq N \leq 500$），由正方形的草地“单元格”组成（可以想象成一个巨大的棋盘）。 由于土壤差异，有些单元格里的草比其他单元格更绿。 每个单元格 $(i,j)$ 用一个整数的绿色程度 $G(i,j)$ 描述，取值范围为 $1 \ldots 200$。 农夫约翰想要拍摄牧场中某个矩形子网格的照片。 他希望这个子网格看起来足够绿，但又不要绿得离谱，因此他决定拍摄一个子网格，使得其中 $G$ 的最小值恰好为 100。 请帮助他确定他一共可能拍出多少种不同的照片。 一个子网格可以大到覆盖整个牧场，也可以小到只包含一个格子（总共有 $N^2(N+1)^2/4$ 个不同的子网格——注意这个数可能大到无法用标准 32 位整数存储，因此你可能需要使用 64 位整数类型，例如 C++ 中的 “long long”）。

输入格式

第一行输入包含 $N$。 接下来的 $N$ 行每行包含 $N$ 个整数，它们共同描述了这个 $N \times N$ 牧场的 $G(i,j)$ 值。

输出格式

请输出农夫约翰可以拍摄的不同照片数量——也就是最小绿色程度恰好为 100 的矩形子网格数量。 注意，本题中涉及的整数可能很大，需要使用 64 位整数类型（例如 C/C++ 中的 “long long”）。

3
57 120 87
200 100 150
2 141 135

8

提示

SCORING: 测试点 1-5 满足 $N\le 200$。 测试点 6-10 没有额外限制。 题目来源：Brian Dean

标签: USACO|2021|Silver

来源

USACO|2021|Silver