#P15686. [Bulgarian2022训练营]running田径

    ID: 14898 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>算法基础前缀和二分数据结构树状数组CF2300

[Bulgarian2022训练营]running田径

题目描述

Sashka 很擅长运动。她非常喜欢在 Hemus 高速公路上跑步,这条高速公路长度为 NN 千米。

Sashka 经过不同的千米路段会获得不同的愉悦值:经过第 ii 千米时,她会获得 aia_i 的愉悦值。

Sashka 有一架私人直升机,可以把她送到第 ll 千米的起点;她跑完之后,直升机会在第 rr 千米的终点接她。若选择区间 [l,r][l,r],其中 1≤l≤r≤N1\le l\le r\le N,她获得的总愉悦值为

al+al+1+⋯+ar.a_l+a_{l+1}+\cdots+a_r.

对 Sashka 来说,长度至少为 LL 千米的路线才有趣,否则太没有挑战性。她会恰好跑 KK 次,每次选择一对不同的端点 (l,r)(l,r),并且要求

r−l+1≥L.r-l+1\ge L.

她希望最大化这 KK 次跑步获得的总愉悦值之和。

请编写程序 running,求出最大可能总愉悦值。

输入格式

第一行包含三个正整数 N,K,LN,K,L。

第二行包含 NN 个整数 a1,a2,…,aNa_1,a_2,\ldots,a_N。

输出格式

输出一行一个整数,表示最大可能总愉悦值。

数据范围

  • 1≤N,K≤3000001\le N,K\le 300000;
  • 1≤L≤N1\le L\le N;
  • ∣ai∣≤106|a_i|\le 10^6;
  • 保证长度至少为 LL 的不同路线数量不少于 KK。

子任务

子任务 分值 NN KK 依赖子任务
1 0 样例 无
2 14 ≤100\le 100 ≤1000\le 1000 1
3 8 ≤1000\le 1000 ≤100000\le 100000 1-2
4 19 ≤10000\le 10000
5 36 ≤50000\le 50000 1-4
6 23 ≤300000\le 300000 1-5

某个子任务得分,要求通过该子任务以及所有依赖子任务中的全部测试点。

样例 1

输入

4 4 2
3 2 -6 8

输出

18

解释

长度在 22 到 44 之间的所有路线为:

  • 1→21\to 2,愉悦值为 55;
  • 2→32\to 3,愉悦值为 −4-4;
  • 3→43\to 4,愉悦值为 22;
  • 1→31\to 3,愉悦值为 −1-1;
  • 2→42\to 4,愉悦值为 44;
  • 1→41\to 4,愉悦值为 77。

最优选择 K=4K=4 条路线,愉悦值之和为 7+5+4+2=187+5+4+2=18。

样例 2

输入

2 1 2
2 -1

输出

1

解释

唯一可能路线为 1→21\to 2,愉悦值为 11。

样例 3

输入

11 21 4
-462 143 441 -637 723 -884 -360 603 -546 -740 -892

输出

-10124