E - Part-Time Job Shift Management Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は、大学生活の傍らでアルバイトをしています。彼の働くお店は繁盛しており、毎日シフトに入ってほしいと頼まれています。

高橋君はこれから N 日間のシフトを組もうとしています。i 日目 (1 \leq i \leq N) について、高橋君はその日に働くか休むかを選びます。i 日目に働いた場合、A_i 円の給料を得られます。休んだ場合、給料は得られません。

しかし、アルバイトばかりしていると学業に支障が出るため、連続して働く日数は K - 1 日以下でなければなりません。すなわち、連続して K 日以上働くようなシフトは組めません。

また、高橋君はお金を稼ぎたいので、連続して休む日数は M - 1 日以下でなければなりません。すなわち、連続して M 日以上休むようなシフトも組めません。

ここで、連続する日数は N 日間の範囲内のみで数えます。1 日目より前や N 日目より後の状態は存在しないものとし、考慮しません。

上記の 2 つの条件をともに満たすシフトの組み方が存在する場合、高橋君が 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
  • 1 行目には、シフトを組む日数 N、連続勤務日数に関する制約 K、連続休暇日数に関する制約 M が、スペース区切りで与えられる。連続して K 日以上働くことはできず、連続して M 日以上休むこともできない。
  • 2 行目には、各日の給料 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • A_i は i 日目に働いた場合に得られる給料である。

出力

条件を満たすシフトの組み方が存在する場合は、高橋君が得られる給料の合計の最大値を 1 行で出力してください。条件を満たすシフトの組み方が存在しない場合は -1 を 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

Score : 466 pts

Problem Statement

Takahashi is working a part-time job alongside his university life. The store where he works is thriving, and he is asked to work every day.

Takahashi is trying to schedule his shifts for the next N days. For day i (1 \leq i \leq N), Takahashi chooses whether to work or take the day off. If he works on day i, he earns a salary of A_i yen. If he takes the day off, he earns no salary.

However, working too much would interfere with his studies, so the number of consecutive days he works must be at most K - 1 days. In other words, he cannot schedule shifts where he works K or more consecutive days.

Additionally, since Takahashi wants to earn money, the number of consecutive days he takes off must be at most M - 1 days. In other words, he cannot schedule shifts where he takes M or more consecutive days off.

Here, consecutive days are counted only within the range of the N days. The state before day 1 or after day N does not exist and is not considered.

If there exists a valid shift schedule that satisfies both of the above conditions, find the maximum total salary Takahashi can earn over the N days. If no valid shift schedule exists, output -1.

Constraints

  • 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
  • All inputs are integers

Input

N K M
A_1 A_2 \ldots A_N
  • The first line contains the number of days to schedule N, the constraint on consecutive working days K, and the constraint on consecutive days off M, separated by spaces. He cannot work K or more consecutive days, and cannot take M or more consecutive days off.
  • The second line contains the salary for each day A_1, A_2, \ldots, A_N, separated by spaces.
  • A_i is the salary earned if he works on day i.

Output

If a valid shift schedule satisfying the conditions exists, output the maximum total salary Takahashi can earn in one line. If no valid shift schedule exists, output -1 in one line.

Sample Input 1

5 3 2
3 5 2 7 4

Sample Output 1

19

Sample Input 2

7 3 3
10 2 8 6 1 9 3

Sample Output 2

36

Sample Input 3

15 4 3
12 5 8 20 3 15 7 11 9 18 6 14 2 10 16

Sample Output 3

137