山东省第八届 ACM 省赛 CF （01背包、水）

山东省第八届 ACM 省赛 CF （01背包、水）

Problem Description

LYD loves codeforces since there are many Russian contests. In an contest lasting for T minutes there are n problems, and for the ith problem you can get ai−di∗ti points, where ai indicates the initial points, di indicates the points decreased per minute (count from the beginning of the contest), and ti stands for the passed minutes when you solved the problem (count from the begining of the contest).Now you know LYD can solve the ith problem in ci minutes. He can’t perform as a multi-core processor, so he can think of only one problem at a moment. Can you help him get as many points as he can?

Input

The first line contains two integers n,T (0≤n≤2000,0≤T≤5000).The second line contains n integers a1,a2,..,an (0

Output

Output an integer in a single line, indicating the maximum points LYD can get.

Example Input

3 10100 200 2505 6 72 4 10

Example Output

254

题意

有 n 道题目，每一道题都有一个初始分值 ai ，每个单位时间这道题的分数便会减少 di ，而我们可以在 ci 时间内做出这道题而得到分数，求在时间 T

思路

假设每道题做出所需要的时间都为 t

假设每道题目不自动消耗分数，那么我们一定会选择题目越快做出越好。

于是，综合以上两种因素得出的公式便是 fi=dici

AC 代码

#include#include#include#include#include#includeusing namespace std;#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。