/ Vijos / 题库 /

炸毁燃料库

炸毁燃料库

背景

某天,外星人展开了对地球的侵略,OIer们开始与之周旋。。。

描述

外星人派出了172849个外星人乘着UFO来到地球,curimit神new带领着OIer们奋力抵抗。curimit神new觉得,仅仅抵抗外星人是不行的,因为外星人还有172849架UFO,必须从根源阻止外星人!
于是curimit神new交给小z一个任务:潜入外星人的基地,摧毁外星人的燃料库。

小z拿着curimit神new给他的地图,来到了外星人的基地。

外星人的燃料库由一排N个燃料筒组成,每个燃料筒中装有一些燃料。小z需要用炸弹炸毁燃料筒。有的燃料筒里面有许多燃料,炸毁它价值就比较高。但有的燃料筒里面只有很少的燃料,甚至没有燃料,所以炸毁它价值很低,甚至不值得去炸毁!于是curimit神new对每个燃料筒有一个估价,有正有负。但是外星人也不是没有防范。在燃料库中有172849个外星人在不停的巡逻,如果小z把任意连续M个燃料筒炸毁K个以上,外星人就会察觉,小z就遭殃了!
于是小z希望你能够帮他定出一个方案,在不被外星人察觉的情况下,能够使自己炸毁的燃料筒的估价和最大(如果所有筒的估价都是负的,那么一个不炸的估价和最大,是0)。

格式

输入格式

第一行有三个数,N,M,K。N<=1000,k<=m<=100。描述见题。

第二行有N个整数,绝对值小于1000,第i个数表示curimit神new对第i个燃料筒的估价。

输出格式

一个数,为满足条件的最大估价和。

样例1

样例输入1

9 5 3
2 3 4 2 3 4 2 3 4

样例输出1

20

限制

各个测试点1s

提示

后记:在小z顺利完成任务之后,curimit神new带领的OIer军队也赶跑了外星人,取得了长久的和平。

此题为经典模型。

信息

ID
1499
难度
6
分类
图结构 | 网络流 点击显示
标签
(无)
递交数
261
已通过
73
通过率
28%
上传者

相关

在下列训练计划中:

RP++分类题库