问题 5466 --竞赛真理-【2014暑期训练】T3Day2T1

5466: 竞赛真理-【2014暑期训练】T3Day2T1

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

题目描述

竞赛真理

【问题描述】

小天天在经历了无数次学科竞赛的失败以后,得到了一个真理:做一题就要对一题!但是要完全正确地做对一题是要花很多时间(包括调试时间),而竞赛的时间有限。所以开始做题之前最好先认真审题,估计一下每一题如果要完全正确地做出来所需要的时间,然后选择一些有把握的题目先做。按照上面的做题方法,有可能出现选择的那几题做完之后还有空的情况(时间有多余),但是这些时间又不足以完全解决一道题目,为了更充分的利用时间,应该把其他的题目用贪心之类的算法随便做做,争取“骗”一点分数。

根据每一题解题时间的估计值,确定一种做题方案(即哪些题目认真做,哪些题目“骗”分,哪些不做),使能在限定的时间内获得最高的得分,

【文件输入】

第一行有两个正整数n和t,表示题目的总数以及竞赛的时限(单位秒)。以下的n行,每行4个正整数w1i  、t1i 、w2i  、t2i ,分别表示第i题:完全正确做出来的得分,完全正确做出来所花费的时间(单位秒),“骗”来的分数,“骗”分所花费的时间(单位秒)。

其中,3≤n≤30,2≤t≤1080000,1≤ w1i 、w2i ≤30000,1≤t1i 、t2i≤t。

【文件输出】

直接把所能得到的最高分值输出到文件truth.out,文件只有一行(包括换行符)。

【样例输入一】

4 10800

18 3600 3 1800

22 4000 12 3000

28 6000 0 3000

32 8000 24 6000

【样例输出一】

50

【样例输入二】

3 7200

50 5400 10 900

50 7200 10 900

50 5400 10 900

【样例输出二】

70

来源

 

[提交][状态]