D. D交集

    传统题 文件IO:d 1000ms 512MiB

D交集

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

在数轴上有 $n$ 条线段,第 $i$ 条线段的左右端点为 $[L_i,R_i]$。

现在蜗蜗需要把这 $n$ 条线段恰好分成 $k$ 组,每一组的价值定义为:该组所有线段的交集长度。并且要求每一组的价值都至少为 $1$

蜗蜗想知道如何分组,使得这 $k$ 组的价值总和最大,输出这个值。

如果无法将 $n$ 条线段恰好分成 $k$ 组,且每一组的价值都至少为 $1$,那么输出 $0$。

输入格式

第一行包含两个整数 $n$, $k$。

接下来 $n$ 行,每行包含两个整数 $L_i, R_i$。

输出格式

输出一行包含一个整数,表示答案。

样例输入 1

4 3
1 2
3 4
5 8
4 5

样例输出 1

7

样例输入 2

4 2
1 2
3 4
5 8
4 5

样例输出 2

0

样例3-9

见附件文件。样例 3-9 分别满足子任务 1-7 的限制。

样例解释

样例 1:

有两种合法的分组方式。

1.分组为:$\{[1,2]\}$,$\{[3,4],[4,5]\}$,$\{[5,8]\}$。价值总和为:$2+1+4=7$。

2.分组为:$\{[1,2]\}$,$\{[3,4]\}$,$\{[5,8],[4,5]\}$。价值总和为:$2+2+1=5$。

所以答案为 $7$。

样例 2:

没有合法的分组方式,所以答案为 $0$。

数据范围

本题采用捆绑测试。

子任务 1(10分):$k=1$。

子任务 2(5分):$k=n$。

子任务 3(10分):$n \leq 15$, $k=2$。

子任务 4(10分):$n \leq 10$, $k \leq 5$。

子任务 5(15分):$n \leq 100$, $k=2$, $L_i \leq R_i \leq 30$。

子任务 6(25分):$n \leq 500$。

子任务 7(25分):无特殊限制。

对于所有数据,保证 $1 \leq k \leq n \leq 5000$, $1 \leq L_i \leq R_i \leq 10^5$。

7.25模拟赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2025-7-25 11:45
结束于
2025-7-25 12:15
持续时间
0.5 小时
主持人
参赛人数
24