← 返回题目列表

AtCoder · codequeen2024_final_c

F. 雨天景点

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

配点 : {400} 点

問題文

高桥君打算乘坐 AtCoder Land 的户外娱乐设施 K 这项娱乐设施一次的所需时间为 T 。

当前的时间是 0 。 0 到 N 会给出到…为止的降水量。时间 i 到 i+1 之前的降水量是 P_i (0\leq i\lt N)。在 time 0,1,…,N−T 可以乘坐娱乐设施。若在 time t 乘坐娱乐设施,将在时间 t+T 从娱乐设施下车,在乘坐娱乐设施的期间会被淋湿 P_t+P_{t+1}+\dots+P_{t+T-1} 。

高桥希望在乘坐景点时尽可能避免在雨中被淋湿。时间 通过 N 经过 K 求高桥在乘坐景点时获得的总湿度的最小值。但转乘时间和等待时间 0 ,下景点后即可乘坐新景点。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq K\leq \min(N,100)
  • 1\leq T\leq N/K
  • 0\leq P_i\leq 10^{9}
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N K T
P_0 P_1 \ldots P_{N-1}

出力

打印答案。


入力例 1

8 3 2
3 5 10 4 1 7 3 9

出力例 1

23

景点如下 3 骑行时的总湿气量 23 ,这是最小值。

  • 景点时间 0 和时间 在 2 下车。这段时间 P_0+P_1=3+5=8 弄湿。
  • 景点时间 3 和时间 在 5 下车。这段时间 P_3+P_4=4+1=5 弄湿。
  • 景点时间 5 和时间 在 7 下车。这段时间 P_5+P_6=7+3=10 弄湿。

入力例 2

5 1 3
1000 1 10000 100 10

出力例 2

10101

入力例 3

15 5 2
401054171 63773035 986525245 157986893 799814573 139201145 649233932 351289844 409065258 406122133 957285954 529460482 21179081 795984182 727882733

出力例 3

3522058414