小 N est responsable d’un entrepôt de légumes et doit concevoir leur plan de vente.
L’entrepôt contient $n$ sortes de légumes. Pour obtenir le revenu maximal, 小 N doit élaborer un plan raisonnable tenant compte de leurs caractéristiques et de tous les facteurs pertinents.
Chaque unité vendue de la sorte $i$ rapporte $a_i$.
En particulier, une politique encourageant la diversité des ventes accorde un revenu supplémentaire de $s_i$ lors de la première vente de la sorte $i$.
Au début de l’activité, le stock de cette sorte est de $c_i$ unités.
La conservation des légumes est toutefois très limitée : une fois avariés, ils ne peuvent plus être vendus. 小 N a déjà calculé quand chaque unité se gâte. Pour la sorte $i$, il existe une valeur de conservation $x_i$ : à la fin de chaque journée, $x_i$ unités se gâtent, jusqu’à ce qu’elles soient toutes avariées. Attention, l’instant où chaque unité se gâte est fixé et ne change pas en fonction des ventes.
Formellement, pour tout entier strictement positif $d$ tel que $d\times x_i\le c_i$, $x_i$ unités se gâtent à la fin du jour $d$.
En particulier, si $(d-1)\times x_i\le c_i<d\times x_i$, alors $c_i-(d-1)\times x_i$ unités se gâtent à la fin du jour $d$.
Si $x_i=0$, les légumes de cette sorte ne se gâtent jamais.
La quantité totale de légumes vendus chaque jour est également limitée : elle ne peut pas dépasser $m$ unités.
小 N vous pose $k$ questions. Chacune donne une valeur $p_j$ : quel est le revenu maximal que l’on peut obtenir en vendant pendant $p_j$ jours ?
Entrée
Les données sont lues dans le fichier vegetables.in.
La première ligne contient trois entiers strictement positifs $n,m,k$, représentant respectivement le nombre de sortes de légumes, la quantité totale maximale vendue par jour et le nombre de questions de 小 N.
Chacune des $n$ lignes suivantes décrit une sorte de légumes par quatre entiers non négatifs $a_i,s_i,c_i,x_i$, définis ci-dessus.
Chacune des $k$ lignes suivantes contient un entier non négatif $p_j$, défini ci-dessus.
Sortie
Écrivez la sortie dans le fichier vegetables.out.
Affichez $k$ lignes contenant chacune un entier ; la $i$-ième est la réponse à la $i$-ième question.
Exemples
Entrée 1
2 3 2 3 3 3 3 2 5 8 3 1 3
Sortie 1
16 27
Exemples 2
Voir vegetables/vegetables2.in et vegetables/vegetables2.ans dans le répertoire du candidat.
Exemples 3
Voir vegetables/vegetables3.in et vegetables/vegetables3.ans dans le répertoire du candidat.
Remarque sur l’exemple 1
Il existe deux sortes de légumes :
La sorte 1 rapporte 3 par unité vendue et un bonus de 3 lors de sa première vente. Son stock contient 3 unités, qui se gâtent toutes à la fin du premier jour.
La sorte 2 rapporte 2 par unité vendue et un bonus de 5 lors de sa première vente. Sur ses 8 unités, 3 se gâtent à la fin du premier jour, 3 à la fin du deuxième et 2 à la fin du troisième.
Si l’on ne vend que pendant 1 jour, il faut vendre 2 unités de la première sorte et 1 unité de la seconde.
Le revenu de la première sorte vaut alors $2\times3+3$, et celui de la seconde $1\times2+5$, pour un total de $(2\times3+3)+(1\times2+5)=16$.
Si l’on vend pendant 3 jours, il faut vendre 3 unités de la première sorte le premier jour, puis 3 unités de la seconde le deuxième jour, en choisissant celles qui se gâteront à la fin de ce deuxième jour, et enfin 2 unités de la seconde le troisième jour.
Le revenu de la première sorte vaut alors $3\times3+3$, et celui de la seconde $(3+2)\times2+5$, pour un total de $(3\times3+3)+[(3+2)\times2+5]=27$.
Sous-tâches
| Numéro du test | $n$ | $m$ | $p_j$ | Propriété 1 | Propriété 2 |
|---|---|---|---|---|---|
| $1$ | $\le 2$ | $\le 10$ | $\le 10^3$ | Non | Non |
| $2$ | $\le 3$ | $\le 10$ | $\le 10^3$ | Non | Non |
| $3$ | $\le 4$ | $\le 10$ | $\le 10^3$ | Non | Non |
| $4$ | $\le 10^3$ | $\le 10$ | $\le 2$ | Non | Non |
| $5$ | $\le 10^3$ | $\le 10$ | $\le 3$ | Non | Non |
| $6$ | $\le 10^3$ | $\le 10$ | $\le 4$ | Non | Non |
| $7$ | $\le 4$ | $\le 1$ | $\le 4$ | Non | Non |
| $8$ | $\le 6$ | $\le 2$ | $\le 6$ | Non | Non |
| $9$ | $\le 8$ | $\le 1$ | $\le 8$ | Non | Non |
| $10$ | $\le 10$ | $\le 2$ | $\le 10$ | Non | Non |
| $11$ | $\le 20$ | $\le 3$ | $\le 20$ | Non | Non |
| $12$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Oui | Non |
| $13$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Non | Oui |
| $14$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Non | Non |
| $15$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | Non | Non |
| $16$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Oui | Oui |
| $17$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Oui | Non |
| $18$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Non | Oui |
| $19$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Non | Non |
| $20$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | Non | Non |
| $21$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Oui | Oui |
| $22$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Oui | Non |
| $23$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Non | Oui |
| $24$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Non | Non |
| $25$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | Non | Non |
Propriété 1 : tous les $s_i$ valent $0$.
Propriété 2 : tous les $x_i$ valent $0$.
Pour tous les tests, les $p_j$ des $k$ questions sont deux à deux distincts.
Pour tous les tests, $0<a_i,c_i\le10^9$ et $0\le s_i,x_i\le10^9$.