#P11724. [JOIG 2025] ポスター 2 / Poster 2

[JOIG 2025] ポスター 2 / Poster 2

题目描述

JOI 学院的理惠为三月举行的文化节制作了一张海报。海报可以视为一个 N×NN\times N 的网格;有 KK 种颜色,编号分别为 11KK,每个格子的颜色是 KK 种颜色之一;具体地,网格的颜色可以用一个矩阵 AA 来表示:记第 ii 行第 jj 列的格子为 (i,j)(1i,jN)(i,j)(1\le i,j\le N),那么 (i,j)(i,j) 的颜色为 Ai,j(1Ai,jK)A_{i,j}(1\le A_{i,j}\le K)

学生希望海报的颜色可以丰富一点;他们定义一张海报的“鲜艳程度”为满足以下条件的 (i,j)(1i,jN1)(i,j)(1\le i,j\le N-1) 的个数:

  • (i,j),(i+1,j),(i,j+1),(i+1,j+1)(i,j),(i+1,j),(i,j+1),(i+1,j+1) 中出现的颜色种类数不小于 33

AA 中出现元素种类数不小于 332×22\times 2 子矩阵个数。

例如,下图中的海报的鲜艳程度为 22,因为存在 22 个满足上述条件的 2×22\times 2 子矩阵(已使用蓝框标出)。

由于时间紧迫,学生们希望通过恰好一次以下操作,或者不进行操作,来最大化海报的鲜艳程度:

  • 选择恰好一个格子 (i,j)(i,j) 和一个与该格子原先颜色不同的颜色 c(1cK)c(1\le c\le K),将格子 (i,j)(i,j) 的颜色改为 cc,即 Ai,jcA_{i,j}\gets c

请求出最终能得到的海报的最大鲜艳程度。

输入格式

第一行输入两个整数 N,KN,K

接下来 NN 行,每行输入 NN 个整数 Ai,jA_{i,j}

输出格式

输出一行一个整数,表示最终能得到的海报的最大鲜艳程度。

2 3
1 2
2 1
1
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
5
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
16
3 3
1 2 3
2 2 2
3 2 1
2
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
39

提示

【样例解释 #1】

如下图所示,将 (2,2)(2,2) 的颜色改为颜色 33,可以使得鲜艳程度为 11

可以证明不存在更优的方案。

该样例满足子任务 1,3,4,51,3,4,5 的限制。

【样例解释 #2】

如下图所示,将 (2,3)(2,3) 的颜色改为颜色 44,可以使得鲜艳程度为 55

可以证明不存在更优的方案。

该样例满足子任务 3,4,53,4,5 的限制。

【样例解释 #3】

该样例满足子任务 2,4,52,4,5 的限制。

【样例解释 #4】

该样例满足子任务 3,4,53,4,5 的限制。

【样例解释 #5】

该样例满足子任务 4,54,5 的限制。

【数据范围】

  • 2N2702\le N\le 270
  • 3K1093\le K\le 10^9
  • 1Ai,jK(1i,jN)1\le A_{i,j}\le K(1\le i,j\le N)

【子任务】

  1. 99 分)N=2,K=3N=2,K=3
  2. 66 分)Ai,j(1i,jN)A_{i,j}(1\le i,j\le N) 两两不同;
  3. 2727 分)N,K10N,K\le 10
  4. 2626 分)N10N\le 10
  5. 3232 分)无附加限制。