#P11724. [JOIG 2025] ポスター 2 / Poster 2
[JOIG 2025] ポスター 2 / Poster 2
题目描述
JOI 学院的理惠为三月举行的文化节制作了一张海报。海报可以视为一个 的网格;有 种颜色,编号分别为 到 ,每个格子的颜色是 种颜色之一;具体地,网格的颜色可以用一个矩阵 来表示:记第 行第 列的格子为 ,那么 的颜色为 。
学生希望海报的颜色可以丰富一点;他们定义一张海报的“鲜艳程度”为满足以下条件的 的个数:
- 中出现的颜色种类数不小于 。
即 中出现元素种类数不小于 的 子矩阵个数。
例如,下图中的海报的鲜艳程度为 ,因为存在 个满足上述条件的 子矩阵(已使用蓝框标出)。
由于时间紧迫,学生们希望通过恰好一次以下操作,或者不进行操作,来最大化海报的鲜艳程度:
- 选择恰好一个格子 和一个与该格子原先颜色不同的颜色 ,将格子 的颜色改为 ,即 。
请求出最终能得到的海报的最大鲜艳程度。
输入格式
第一行输入两个整数 。
接下来 行,每行输入 个整数 。
输出格式
输出一行一个整数,表示最终能得到的海报的最大鲜艳程度。
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】
如下图所示,将 的颜色改为颜色 ,可以使得鲜艳程度为 。
可以证明不存在更优的方案。
该样例满足子任务 的限制。
【样例解释 #3】
该样例满足子任务 的限制。
【样例解释 #4】
该样例满足子任务 的限制。
【样例解释 #5】
该样例满足子任务 的限制。
【数据范围】
- ;
- ;
- 。
【子任务】
- ( 分);
- ( 分) 两两不同;
- ( 分);
- ( 分);
- ( 分)无附加限制。