Vegetables - MarisaOJ: Marisa Online Judge

Vegetables

Time limit: 2000 ms
Memory limit: 512 MB
You are managing a store selling vegetables and have to plan the sales. There are $n$ types of vegetables, and each unit of vegetable type $i$ sold will earn $a_i$. Furthermore, to enhance diversity, the first time selling vegetable type $i$ will receive an additional $s_i$. On the first day, vegetable type $i$ has $c_i$ units. However, the freshness of vegetable type $i$ is $x_i$, meaning at the end of each day, $x_i$ units will wither. Moreover, each day, you cannot sell more than $m$ units of vegetables. The director asks you $k$ questions. For the $j$-th question, a non-negative integer $p_j$ is asked, inquiring about the maximum profit if you have to sell for $p_j$ days. ### Input - The first line consists of three integers $n, m, k$. - The next $n$ lines, the $i$-th line contains four integers $a_i, s_i, c_i, x_i$. - The next $k$ lines, the $j$-th line contains a non-negative integer $p_j$. ### Output - Output $k$ lines, the $i$-th line is the answer to the $i$-th question. ### Example Input: ``` 2 3 2 3 3 3 3 2 5 8 3 1 3 ``` Output: ``` 16 27 ``` Explanation: - For the case of $1$ day: Buy $1$ unit of vegetable type $2$ and $2$ units of vegetable type $1$. - For the case of $3$ days: + On the first day, buy $3$ units of vegetable type $1$, earning $12$. At the end of the day, there are still $5$ units of vegetable type $2$. + On the second day, buy $3$ units of vegetable type $2$, earning $11$. There should be $3$ units of vegetable type $2$ withering at the end of the day, but we sold them, leaving $2$ units of vegetable type $2$. + On the third day, sell the remaining $2$ units of vegetable type $2$, earning $4$, making the total $12 + 11 + 4 = 27$. ### Constraints - Condition $1$: All $s_i$ values are $0$. - Condition $2$: All $x_i$ values are $0$. - Ensure distinct values for each $p_j$. - $0 \le a_i, c_i, s_i, x_i \le 10^9$.
Test $n$ $m$ $p_j$ Condition $1$ Condition $2$
1 $\le 2$ $\leq 10$ $\leq 10^3$ No
2 $\le 3$
3 $\le 4$
4 $\le 10^3$ $\le 2$
5 $\le 3$
6 $\le 4$
7 $\leq 4$ $\leq 1$
8 $\leq 6$ $\leq 2$ $\leq 6$
9 $\leq 8$ $\leq 1$ $\leq 8$
10 $\leq 10$ $\leq 2$ $\leq 10$
11 $\leq 20$ $\leq 3$ $\leq 20$
12 $\leq 10^2$ $\leq 10$ $\leq 10^2$ Yes No
13 No Yes
14 No
15
16 $\leq 10^3$ $\leq 10^3$ Yes Yes
17 No
18 No Yes
19 No
20
21 $\leq 10^5$ $\leq 10^5$ Yes Yes
22 No
23 No Yes
24 No
25