#P11859. [CCC 2025 Senior] 画画 / Pretty Pens
[CCC 2025 Senior] 画画 / Pretty Pens
题目背景
译自 CCC 2025 Senior T3。本题满分为 。
题目描述
有 支笔, 种颜色。第 支笔的颜色为 ,美丽度为 。
现在要用这些笔来画画。画会用到 种颜色,所以要从每种颜色的笔中各选出一支,画的美丽度就是选出的笔的美丽度之和。
在下笔前,你可以选择至多一支笔,将这支笔的颜色改成 中的任意一种。画完后,这支笔的颜色将恢复为原本的颜色。
有 次操作:
- :令 。
- :令 。
对于 ,求出:在完成前 次操作后,用这些笔画出画的美丽度最大值。
再次强调,画完一幅画后,这支笔的颜色将恢复为原本的颜色。
输入格式
第一行,三个非负整数 。
接下来 行,每行两个正整数 。
接下来 行,每行三个正整数,描述一个操作。
数据保证,在任意时刻,每种颜色都至少有一支笔。
输出格式
输出 行,第 行的正整数表示完成前 次操作后,用这些笔画出画的美丽度最大值。
6 3 0
1 6
2 9
3 4
2 7
3 9
1 3
25
3 2 2
1 20
2 30
1 10
1 3 2
2 3 25
50
50
55
提示
样例解释
- 样例 解释:
起初,有三种颜色的笔:
- 颜色 的笔的美丽度为 。
- 颜色 的笔的美丽度为 。
- 颜色 的笔的美丽度为 。
如果不改变笔的颜色,画的最大美丽度为 。
然而,将第 支笔的颜色从 改成 可以获得 的美丽度,这也是最优方案。
- 样例 解释:
在第一次修改前和第二次修改前,选择第 支笔是最优的。
在第二次修改后,选择第 支笔是最优的。
子任务
对于 的数据,保证:
- ;
- ;
- ;
- ;
- ;
- 在任意时刻,每种颜色都至少有一支笔。
子任务 为样例。
特殊性质 | 得分 | ||||
---|---|---|---|---|---|
/ | |||||
/ |
- 特殊性质 :数据保证在任意时刻, 支笔的美丽度都是两两不同的。