Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Bienvenue dans le TV Time de M. Ant Tenna ! Dans cette manche du jeu, on vous donne $n$ seaux, où le $i$-ème seau a une capacité maximale de $v_i$ volumes d'eau. Au début du jeu, tous les seaux sont entièrement remplis d'eau, et votre mission est d'en conserver autant que possible pendant les $t$ prochaines secondes. Mais voici le piège : ces seaux sont percés ! Le $i$-ème seau a une vitesse de fuite de $l_i$, ce qui signifie qu'à chaque seconde après le début du jeu, le $i$-ème seau laisse s'échapper $l_i$ volumes d'eau.

Avant le début du jeu, vous pouvez fusionner un nombre quelconque de seaux en un seul. Le seau résultant a une capacité égale à la capacité maximale parmi les seaux fusionnés, et une vitesse de fuite égale à la vitesse de fuite minimale parmi les seaux fusionnés. Vous pouvez effectuer des fusions autant de fois que vous le souhaitez, mais elles doivent être réalisées avant de remplir les seaux d'eau.

Tenna pose $q$ questions, où la $i$-ème question a une limite de temps $t_i$. Pour chaque $1 \le i \le q$, calculez le volume total maximal conservé après $t_i$ secondes. Notez que chaque question est indépendante.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 5 \times 10^4$) indiquant le nombre de cas de test. Pour chaque cas de test :

La première ligne contient un entier $n$ ($1 \le n \le 2 \times 10^5$), indiquant le nombre de seaux.

La deuxième ligne contient $n$ entiers $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), où $v_i$ est la capacité du $i$-ème seau.

La troisième ligne contient $n$ entiers $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), où $l_i$ est la vitesse de fuite du $i$-ème seau.

La quatrième ligne contient un entier $q$ ($1 \le q \le 2 \times 10^5$), indiquant le nombre de questions.

La cinquième ligne contient $q$ entiers $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), où $t_i$ est la limite de temps pour la $i$-ème requête.

Il est garanti que ni la somme de $n$ ni la somme de $q$ sur tous les cas de test ne dépassera $2 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une ligne contenant $q$ entiers séparés par un espace, où le $i$-ème entier est le volume total maximal conservé après $t_i$ secondes.

Exemples

2
4
5 4 7 6
2 1 3 2
3
3 1 2
4
19 47 21 13
5 14 2 3
5
5 2 6 1 4
4 14 8
43 67 38 77 48

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.