Responsive image

问题 E: 学院收益1

问题 E: 学院收益1

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

题目描述

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

输入描述

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

输出描述

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

样例输入

2 5 2
1 2 3 6 5

样例输出

8

提示

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

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

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