← 返回题目列表

AtCoder · joig2025_b

B. 海报2(海报2)

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

配点: 100 点

問題文

JOI学园的理惠是 3 我为四月举行的学园祭制作了海报。 这张海报是 N 行 N 它是一列方格的形式,每个方格是 编号至 1 我决定将所有值添加到 K 编号最多为 K 使用以下颜色之一绘制。 具体来说,从海报的顶部 i 行,从左起 j 列目 (1 \leqq i \leqq N,1 \leqq j \leqq N) 是颜色 它涂有 A_{i,j} 。

不过,当学生们讨论这张海报时,他们觉得还是把它弄得更丰富多彩一点会更好。 具体定义如下色彩 有人认为增加会更好。

  • 连续 2 行 2 在该列的正方形区域中,3 包含多种颜色的对象数量。

例如,如果您创建如下图左侧所示的海报, 2 关于矩形区域 3 由于它包含不止一种颜色,因此色彩鲜艳度为 2 。

距离海报提交截止日期仅剩几分钟,因此请按照以下步骤操作。 0 次或 我们希望通过执行此 1 次来最大化色彩。

  • 选择您最喜欢的方块 1 选择一个并更改该方块的颜色。 K 使用以下颜色之一重新绘制。

给定 Rie 制作的第一张海报的信息,编写一个程序来找到可以实现的最大色彩。

制約

  • 2 \leqq N \leqq 270.
  • 3 \leqq K \leqq 10^9.
  • 1 \leqq A_{i,j} \leqq K (1 \leqq i \leqq N,1 \leqq j \leqq N).
  • 所有输入值都是整数。

小課題

  1. (9 点) N = 2,K = 3.
  2. (6 点) A_{i,j} (1 \leqq i \leqq N,1 \leqq j \leqq N)都是不同的。
  3. (27 点) N \leqq 10,K \leqq 10.
  4. (26 点) N \leqq 10.
  5. (32 点)没有额外的限制。

入力

输入按以下格式给出。

N K
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}

出力

可实现的最大色彩 1 行。


入力例 1

2 3
1 2
2 1

出力例 1

1

从上面看,如下图。 2 行,从左起 2 为列中的单元格着色 通过用 3 重新绘制,色彩的程度 1 可以实现。

色彩 有人认为增加 2 没有办法实现这一点,所以1 输出该值。

此输入示例是一个小作业。 1, 3, 4, 5 。


入力例 2

5 5
1 1 1 2 2
1 1 1 2 2
3 3 1 2 2
3 3 5 5 5
3 3 5 5 5

出力例 2

5

从上面看,如下图。 2 行,从左起 3 为列中的单元格着色 通过用 4 重新绘制,色彩的程度 5 可以实现。

色彩 有人认为增加 6 没有办法实现这一点,所以5 输出该值。

此输入示例是一个小作业。 3, 4, 5 。


入力例 3

5 1000000000
104289385 946930886 881692778 914636916 257747795
524238335 819885386 849760493 696516649 389641422
225202363 550490028 883368690 302520060 344897765
267513928 565180541 740383427 404089172 503455737
135005211 621595368 394702567 926956430 436465782

出力例 3

16

此输入示例是一个小作业。 2, 4, 5 。


入力例 4

3 3
1 2 3
2 2 2
3 2 1

出力例 4

2

此输入示例是一个小作业。 3, 4, 5 。


入力例 5

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

出力例 5

39

此输入示例是一个小作业。 4, 5 。