#1909. 新居规划
新居规划
新居规划
题目描述
标题: 新居规划 - Problem - QOJ.ac
#10307. 新居规划
随着苏州的建设与发展,越来越多人选择来到苏州开始新生活。
在一片新建的小区里,有 m 栋围成一圈的房子,房子从 1 到 m 编号,房子 i 与 房子 i+1 相邻,特别地,房子 1 和房子 m 也相邻。
小 Z 需要为 n 个人安排住宿,对于第 i 个人来说:
- 如果 i 没有被安排住宿,那么他的满意度是 0;
- 如果 i 被安排了住宿,那么他的满意度是 ai;
- 如果 i 被安排了住宿且其拥有邻居(即他的某个相邻房子也被安排了住宿),那么他的满意度额外加 bi(也即总满意度为 ai+bi)。
小 Z 希望每个被安排了住宿的人都住进不同的房子,现在他想知道怎么样安排才能最大化所有人的总满意度。
输入格式
从标准输入读入数据。
本题的测试点包含有多组测试数据
输入的第一行包含两个整数 s 和 t,分别表示子任务编号和测试数据组数。对于样 例,s 表示该样例与子任务 s 拥有相同的限制条件。
接下来,对于每组测试数据:
- 输入第一行包含两个整数 n,m,表示人数和房子数。
- 接下来 n 行,每行包含两个整数 ai,bi,意义如题面所述。
输出格式
输出到标准输出。
每组数据输出一行一个整数,表示最大的总满意度。
样例
输入
8 5
2 2
70 63
55 63
7 7
-18 10
-8 -14
-20 -3
-2 -13
22 -40
15 -34
17 -39
4 1
-42 49
24 15
-27 43
-22 2
2 2
-17 23
12 -18
4 4
3 -42
3 -16
54 -10
51 -57
输出
251
54
39
12
105
样例二
见下载目录下的 ex_2.in 与 ex_2.ans。
该组样例满足子任务 4 的条件。
样例三
见下载目录下的 ex_3.in 与 ex_3.ans。
该组样例满足子任务 7 的条件。
样例四
见下载目录下的 ex_4.in 与 ex_4.ans。
该组样例满足子任务 8 的条件。
子任务
对于所有测试数据,保证 1≤t≤10,1≤n≤2×105,0≤m≤109,−109≤ai,bi≤109。
子任务得分n≤特殊性质1515无22031550041035255×1046202×10575A810B
特殊性质 A:∀1≤i≤n,ai≤0;
特殊性质 B:∀1≤i≤n,ai≥0。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
8 5
2 2
70 63
55 63
7 7
-18 10
-8 -14
-20 -3
-2 -13
22 -40
15 -34
17 -39
4 1
-42 49
24 15
-27 43
-22 2
2 2
-17 23
12 -18
4 4
3 -42
3 -16
54 -10
51 -57
251
54
39
12
105