【NOI2017】蔬菜 排行榜


时间限制: 3 s
空间限制: 512 MB

题目描述

小N是蔬菜仓库的管理员,负责设计蔬菜的销售方案。

在蔬菜仓库中,共存放有 $n$ 种蔬菜,小N需要根据不同蔬菜的特性,综合考虑各方面因素,设计合理的销售方案,以获得最多的收益。

在计算销售蔬菜的收益时,每销售一个单位第 $i$ 种蔬菜,就可以获得 $a_i$ 的收益。

特别地,由于政策鼓励商家进行多样化销售,第一次销售第 $i$ 种蔬菜时,还会额外得到 $s_i$ 的额外收益。

在经营开始时,第 $i$ 种蔬菜的库存为 $c_i$ 个单位。

然而,蔬菜的保鲜时间非常有限,一旦变质就不能进行销售,不过聪明的小N已经计算出了每个单位蔬菜变质的时间 :对于第 $i$ 种蔬菜,存在保鲜值 $x_i$,每天结束时会有 $x_i$ 个单位的蔬菜变质,直到所有蔬菜都变质。(注意:每一单位蔬菜的变质时间是固定的,不随销售发生变化)

形式化地:对于所有的满足条件 $d \times x_i \le c_i$ 的正整数 $d$ ,有 $x_i$ 个单位的蔬菜将在第 $d$ 天结束时变质。

特别地,若 $(d-1)\times x_i \le c_i < d\times x_i$ ,则有 $c_i - (d-1)\times x_i$ 单位的蔬菜将在第 $d$ 天结束时变质。

注意,当 $x_i = 0$ 时,意味着这种蔬菜不会变质。

同时,每天销售的蔬菜总量也是有限的,最多不能超过 $m$ 个单位。

现在,小N有 $k$ 个问题,想请你帮忙算一算。每个问题的形式都是:对于已知的 $p_j$,如果需要销售 $p_j$ 天,最多能获得多少收益?

输入格式

从标准输入读入数据。

第一行包含三个正整数 $n,m,k$,分别表示蔬菜的种类数目、每天能售出蔬菜总量上限、小N提出的问题的个数。

接下来 $n$ 行,每行输入四个非负整数,描述一种蔬菜的特点,依次为 $a_i,s_i,c_i,x_i$ ,意义如上文所述。

接下来 $k$ 行,每行输入一个非负整数 $p_j$ ,意义如上文所述。

输出格式

输出到标准输出。

输出 $k$ 行,每行包含一个整数,第 $i$ 行的数表示第 $i$ 个问题的答案。

样例输入

样例输出

样例解释

共有两种蔬菜:

销售第 $1$ 种蔬菜时,每销售一单位可以获得的收益为 $3$ ,第一次销售这种蔬菜时,额外可以获得的收益为 $3$。这种蔬菜共有 $3$ 个单位,均会在第一天结束时变质。

销售第 $2$ 种蔬菜时,每销售一单位可以获得的收益为 $2$ ,第一次销售这种蔬菜时,额外可以获得的收益为 $5$。这种蔬菜共有 $8$ 个单位,其中,有 $3$ 单位在第一天结束时变质, $3$ 单位在第二天结束时变质, $2$ 单位在第三天结束时变质。

在只销售 $1$ 天时,应当销售 $2$ 单位的第一种蔬菜和 $1$ 单位的第二种蔬菜。

在这种情况下:销售第一种蔬菜的收益为 $2\times 3 + 3$ ;销售第二种蔬菜的收益为 $1\times 2 +5$ ;总共获得的收益为 $(2\times 3 + 3)+(1\times 2 +5) = 16$ 。

在只销售 $3$ 天时,第一天应当销售 $3$ 单位的第一种蔬菜,第二天应当销售 $3$ 单位的第二种蔬菜(此时选择在第二天结束时会变质的 $3$ 个单位出售),第三天销售 $2$ 单位的第二种蔬菜。

在这种情况下:销售第一种蔬菜的收益为 $3\times 3 + 3$ ;销售第二种蔬菜的收益为 $(3+2)\times 2 +5$ ;总共获得的收益为 $(3\times 3 + 3)+[(3+2)\times 2 + 5] = 27$ 。

数据范围

测试点编号$n$$m$$p_j$特性1特性2
1$\le 2$$\le 10$$\le 10^3$
2$\le 3$
3$\le 4$
4$\le 10^3$$\le 2$
5$\le 3$
6$\le 4$
7$\le 4$$\le 1$
8$\le 6$$\le 2$$\le 6$
9$\le 8$$\le 1$$\le 8$
10$\le 10$$\le 2$$\le 10$
11$\le 20$$\le 3$$\le 20$
12$\le 10^2$$\le 10$$\le 10^2$
13
14
15
16$\le 10^3$$\le 10^3$
17
18
19
20
21$\le 10^5$$\le 10^5$
22
23
24
25

特性 1:所有的 $s_i$ 均为 $0$。

特性 2:所有的 $x_i$ 均为 $0$。

对于所有的测试数据,均保证 $k$ 组询问中的 $p_j$ 互不相同。

对于所有的测试数据,均保证 $0 < a_i , c_i \le 10^9$ , $0 \le s_i , x_i \le 10^9$ 。

题目来源

NOI 2017 Day 2


关于标准输出的说明(最后更新:2018年10月23日)

标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。

如果你的程序要进行大量输出,请考虑这一点。




Judge Duck Online | 评测鸭在线
Server Time: 2019-10-16 22:05:28 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用