Responsive image

问题 F: 学院收益2

问题 F: 学院收益2

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 16
[提交][状态][讨论版][命题人:]

题目描述

(本题与1的唯一区别是要求学院是连续的）
来福小二最近沉迷于文明六，他在游戏中遇到了一个困难：
由于来福小二的科技落后，所以他需要在 m 个地块上建造至少 n-1 个学院来提高科技值。(至少n个学院－－－学院数量>=n-1)
建立一所学院需要 x 点生产力，建成后会获得 y 点生产力（不同的地块，消耗的 x 相同，获得的 y 不同）
现在他想要知道建造 至少n个学院的最大收益是多少（收益 = 获得y－消耗x )
同时由于来福小二想要这些学院是连在一起的（即学院的地址是连续的）

输入描述

第一行三个整数 n，m，x。表示 n 个学院 m 个地块和建一所学院的花费 x 
第二行共 m 个整数表示在第 i 个地块上建一个学院所产生的生产力 yi 
数据保证:  0<=x<=1e9 , 0<=yi<=1e9 , 1<= m<=1e6 , 1<=n<=m ;

输出描述

一个整数，表示最多收益（可以为负数）

样例输入

2 5 2
1 2 3 6 5

样例输出

8

提示

在样例中，选择 3，4，5 的地块 



生产力的收益=3-2+6-2+5-2=8，此时产生的收益最大

[提交][状态]
ACM算法攻关部