← 返回题目列表

Codeforces · 1500/D

D. 浴室瓷砖

中文机器翻译题面 查看原题

Kostya 非常忙碌:他正在装修他的房子!他需要手工壁纸、组装家具、扔掉垃圾。

Kostya 今天正在购买浴室瓷砖。他站在一家商店里一个铺着瓷砖的大方形摊位前。支架是一个由 $$$n \times n$$$ 个单元格组成的正方形,每个单元格包含一个颜色为 $$$c_{i,\,j}$$$ 的小瓷砖。商店出售成包的瓷砖:更具体地说,您只能购买初始方块的一个子方块。

子正方形是看台的任何正方形部分,即。 e.任何集合 $$$S(i_0, j_0, k) = \{c_{i,\,j}\ |\ i_0 \le i < i_0 + k, j_0 \le j < j_0 + k\}$$$ 与 $$$1 \le i_0, j_0 \le n - k + 1$$$。

Kostya 仍然不知道他需要多少块瓷砖,因此他考虑了所有可能尺寸的子方格。他不希望他的浴室色彩过于鲜艳。帮助 Kostya 计算每个 $$$k \le n$$$ 大小为 $$$k \times k$$$ 且最多具有 $$$q$$$ 不同颜色瓷砖的子方块的数量。如果两个子方格在展台上的位置不同,则它们被视为不同。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 1500$$$, $$$1 \le q \le 10$$$) - 展台的大小和子正方形中不同颜色数量的限制。

接下来的 $$$n$$$ 行包含 $$$n$$$ 整数 $$$c_{i,\,j}$$$ ($$$1 \le c_{i,\,j} \le n^2$$$):第 $$$i$$$ 行中的第 $$$j$$$ 整数是单元格中图块的颜色$$$(i,\,j)$$$。

输出

对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$ 打印一个整数 - 大小为 $$$k \times k$$$ 且不超过 $$$q$$$ 不同颜色的子方格数。

示例

输入 #1

3 4
1 2 3
4 5 6
7 8 9

输出 #1

9
4
0

输入 #2

4 8
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7

输出 #2

16
9
4
0

注意

在第一个示例中,所有颜色都是不同的。 Kostya 不希望子方块的颜色超过 $$$4$$$ 颜色,因此他可以购买任何大小为 $$$1 \times 1$$$ 或 $$$2 \times 2$$$ 的子方块,但他不能购买大小为 $$$3 \times 3$$$ 的子方块。

在第二个示例中,有些颜色出现了多次。因为 $$$q = 8$$$,Kostya 可以购买任何大小为 $$$1 \times 1$$$ 和 $$$2 \times 2$$$ 的子方格,以及任何 $$$3 \times 3$$$ 的子方格,因为这样的子方格有 $$$7$$$ 不同的颜色。他不能买整个摊位 $$$4 \times 4$$$,因为有 $$$9$$$ 颜色。