← 返回题目列表

AtCoder · awc0042_e

E. 兼职轮班管理

中文机器翻译题面 查看原题

分数: 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