#P17220. [2025年南开中学集训]构造排位

    ID: 16379 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-带权二分图匹配前后缀最值辅助点压缩边消除被支配候选指定流量最小费用流势能优化费用流Dinic当前弧优化

[2025年南开中学集训]构造排位

题目描述

大 HH 举办了一个大型锦标赛。锦标赛由若干场比赛组成,并且有很多的选手。每场的参赛人数为 nn。这 nn 个人参加比赛之后都会获得一个排名,排名是 11 到 nn 的整数,并且这些排名两两不同。

如今,HPLHPL 决赛举办在即,共筛选出了 nn 名选手参加,编号为 1∼n1\sim n。

ii 号选手在之前的赛事中排名小于等于 jj 的比赛有 ci,jc_{i,j} 次,每个选手的最后的得分会根据 ci,jc_{i,j} 给出。根据定义,保证有 ci,j≤ci,j+1c_{i,j}\le c_{i,j+1}。

注:不一定满足每人的总场次相同,不一定满足每个排名的总人次相同。你也不需要关心在决赛之前的比赛具体的信息。

决赛打 kk 场,这 kk 场排名未知,但所有情况都有可能出现。每场都会将排名算入表现,最后得到 ci,j′c'_{i,j}。

最终选手 ii 的得分为 si=max⁡1≤j≤n(ci,j′−j)s_i=\max_{1\le j\le n}(c'_{i,j}-j)(sis_i 可能为负数)。比赛的精彩值为所有选手得分之和 ∑i=1nsi\sum_{i=1}^{n}s_i。

你想知道精彩值最大可能为多少。

输入格式

第一行两个数 n,kn,k。

接下来 nn 行每行 nn 个数,第 ii 行第 jj 个数为 ci,jc_{i,j}。

输出格式

第一行输出一个数,表示最大可能的精彩值。

样例 1 输入

3 1
0 1 3
1 1 2
1 2 2

样例 1 输出

3

样例 1 解释

让 22 号获得第一名,33 号获得第二名,11 号获得第三名。

新的表现分 ci,j′c'_{i,j} 变为:

0 1 4
2 2 3
1 3 3

有 s1=c1,3′−3=1s_1=c'_{1,3}-3=1,s2=c2,1′−1=1s_2=c'_{2,1}-1=1,s3=c3,2′−2=1s_3=c'_{3,2}-2=1。

样例 2 输入

5 3
0 0 1 1 2
0 1 1 2 2
1 1 2 2 3
1 2 2 3 3
2 2 3 3 4

样例 2 输出

10

说明与提示

对于所有数据:2≤n≤16002\le n\le 1600,1≤k≤501\le k\le 50,0≤ci,j≤1060\le c_{i,j}\le 10^6。

子任务 分值 特殊性质
1 10 n,k≤5n,k\le 5
2 20 k=1k=1
3 n≤100n\le 100
4 30 n≤700n\le 700
5 20 无特殊性质