蔬菜(vegatable)

noi2017-Day2-T2

【问题描述】

小N是蔬菜仓库的管理员，负责设计蔬菜的销售方案。
在蔬菜仓库中，共存放有n种蔬菜，小N需要根据不同蔬菜的特性，综合考虑各方面因素，设计合理的销售方案，以获得最多的收益。
在计算销售蔬菜的收益时，每销售一个单位第i种蔬菜，就可以获得ai的收益。
特别地，由于政策鼓励商家进行多样化销售，第一次销售第i种蔬菜时，还会额外得到si的额外收益。
在经营开始时，第i种蔬菜的库存为ci个单位。
然而，蔬菜的保鲜时间非常有限，一旦变质就不能进行销售，不过聪明的小N已经计算出了每个单位蔬菜变质的时间：对于第i种蔬菜，存在保鲜值xi，每天结束时会有xi个单位的蔬菜变质，直到所有蔬菜都变质。（注意：每一单位蔬菜的变质时间是固定的，不随销售发生变化）
形式化地：对于所有的满足条件d * xi <= ci的正整数d,有xi个单位的蔬菜将在第d天结束时变质。
特别地，若(d-1)xi <= ci < dxi,则有ci - (d - 1)*xi单位的蔬菜将在第d天结束时变质。
注意，当 xi=0时，意味着这种蔬菜不会变质。
同时，每天销售的蔬菜总量也是有限的，最多不能超过m个单位。
现在，小N有k个问题，想请你帮忙算一算。每个问题的形式都是：对于已知的pj，如果需要销售pj天，最多能获得多少收益？
（题目描述以pdf文件为准）

【输入形式】

从文件 vegetables.in 中读入数据。第一行包含三个正整数 n, m, k,分别表示蔬菜的种类数目、每天能售出蔬菜总量上限、小 N 提出的问题的个数。接下来 n 行,每行输入四个非负整数,描述一种蔬菜的特点,依次为 a i , s i , c i , x i ,意义如上文所述。接下来 k 行,每行输入一个非负整数 p j ,意义如上文所述。

【输出形式】

输出到文件 vegetables.out 中。输出 k 行,每行包含一个整数,第 i 行的数表示第 i 个问题的答案。

【输入样例1】

见下发文件的 vegetables/vegetables1.in。

【输出样例1】

见下发文件的 vegetables/vegetables1.ans。

【输入样例2】

见下发文件的 vegetables/vegetables2.in。

【输出样例2】

见下发文件的 vegetables/vegetables2.ans。

【输入样例3】

见下发文件的 vegetables/vegetables3.in。

【输出样例3】

见下发文件的vegetables/vegetables3.ans。

【时间限制】

【空间限制】

512000KB

【上传文件】

上传c, cpp, pas语言源程序，文件名为vegetables.c, vegetables.cpp, vegetables.pas。

Upload Your source File(s) :

Note :Your program can be written with the programing language(s) as below
C(.c): your source filename is ''vegetables.c''
CPP(.cpp): your source filename is ''vegetables.cpp''
PAS(.pas): your source filename is ''vegetables.pas''

我知道是用贪心的策略，
但无论是单独贪心多卖还是单独贪心高价明显都会有对应的数据卡分，
明智的贪心显然会是其他办法,我暂时没有思路，做过类似的例题，模拟赛中一时记不得了