分数: 466 分
问题陈述
高桥在大学生活的同时还在做兼职工作。他工作的店生意红火,每天都要求他干活。
高桥正在尝试安排下一个班次 N 天。一天 i (1 \leq i \leq N),高桥选择是工作还是休息。如果他白天工作 i,他的工资为 A_i 日元。如果他请假,他就没有工资。
但是,工作太多会影响他的学习,所以他连续工作的天数最多不得超过 K - 1 天。换句话说,他无法在工作地点安排轮班 K 或连续几天。
另外,高桥既然要赚钱,那么他连续起飞的天数最多必须是 M - 1 天。换句话说,他无法安排轮班时间 M 或连续更多天休息。
这里,仅计算连续天数范围内的天数。 N 天。天前的状态 1 或当天之后 N 不存在,不予考虑。
如果存在满足上述两个条件的有效轮班安排,请找出 Takahashi 在 N 天。如果不存在有效的轮班计划,则输出 -1.
约束
- 1 \leq N \leq 2 \times 10^5
- 2 \leq K \leq N + 1
- 2 \leq M \leq N + 1
- 1 \leq A_i \leq 10^9
- 所有输入均为整数
输入
N K M A_1 A_2 \ldots A_N
- 第一行包含要安排的天数 N,连续工作日的限制 K,以及连续休息日的限制 M,用空格分隔。他无法工作 K 或连续几天以上,并且不能采取 M 或连续更多天休息。
- 第二行包含每天的工资 A_1, A_2, \ldots, A_N,用空格分隔。
- A_i 是他白天工作所得的工资 i.
输出
如果存在满足条件的有效排班表,则在一行中输出高桥可以获得的最高工资总额。如果不存在有效的轮班计划,则输出 -1 一行。
示例输入 1
5 3 2 3 5 2 7 4
示例输出 1
19
示例输入 2
7 3 3 10 2 8 6 1 9 3
示例输出 2
36
示例输入 3
15 4 3 12 5 8 20 3 15 7 11 9 18 6 14 2 10 16
示例输出 3
137