#P6881. duke
duke
Duck
题目描述
有 个元素,编号为 至 。你需要把它们排成一个排列。
对于元素 ,如果至少有一个编号属于闭区间 的元素排在它前面,就计入贡献 。如果不存在这样的元素,贡献为 。即使有多个符合条件的元素, 也只计入一次。 可以为负,条件满足时必须计入。元素 本身不会排在自己前面。
求所有排列中贡献之和的最大值。
输入格式
第一行一个整数 。
接下来 行,第 行三个整数 。
输出格式
输出一行一个整数,表示最大总贡献。答案可以为负数。
样例
2
2 2 1
1 1 2
2
2
2 2 -1
1 1 -1
-1
样例 2 中,无论如何排列,后一个元素的贡献均为 。
数据范围
,,。
| 测试集 | 分值 | 的上界 |
|---|---|---|
| 1 | 25 | 5 |
| 2 | 10 | |
| 3 | 20 | |
| 4 | 10 | |
| 5 | ||
| 6 | ||
本 Hydro 训练版补充保证
考虑只包含 的元素的有向图。若 且 ,则这两点之间有一条 的边。每个测试点中,这张图的每个强连通分量至少符合下列一种情况:
- 大小不超过 。
- 分量内每个点恰有一条出边,构成一个有向环。
- 分量内每条边都有反向边。将分量内的点按原编号排序,给每个点补上指向自身的边后,每个点的出邻居占据连续的一段。
只对既不符合第 2 条也不符合第 3 条的分量计算 。每个测试点这一总量至多为 。上述保证只限制测试数据的结构,排列和计分规则如题意所述。