Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 난이도: [표시] 해킹 가능 ✓
통계

Willkommen zu Mr. Ant Tennas TV Time! In dieser Spielrunde erhältst du $n$ Eimer, wobei der $i$-te Eimer ein maximales Fassungsvermögen von $v_i$ Wasservolumen hat. Zu Beginn des Spiels werden alle Eimer vollständig mit Wasser gefüllt, und deine Aufgabe ist es, in den nächsten $t$ Sekunden so viel Wasser wie möglich darin zu behalten. Aber hier ist der Haken: Diese Eimer sind kaputt! Der $i$-te Eimer hat eine Leckrate von $l_i$, was bedeutet, dass in jeder Sekunde nach Spielbeginn aus dem $i$-ten Eimer $l_i$ Wasservolumen herausrinnen.

Vor Spielbeginn darfst du beliebig viele Eimer zu einem einzigen verschmelzen. Der entstehende Eimer hat ein Fassungsvermögen, das dem maximalen Fassungsvermögen der verschmolzenen Eimer entspricht, und eine Leckrate, die der minimalen Leckrate der verschmolzenen Eimer entspricht. Du kannst das Verschmelzen beliebig oft durchführen, allerdings muss dies vor dem Einfüllen des Wassers geschehen.

Tenna stellt $q$ Fragen, wobei die $i$-te Frage ein Zeitlimit $t_i$ hat. Berechne für jedes $1 \le i \le q$ das maximale insgesamt verbleibende Wasservolumen nach $t_i$ Sekunden. Beachte, dass jede Frage unabhängig ist.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 5 \times 10^4$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 2 \times 10^5$), die die Anzahl der Eimer angibt.

Die zweite Zeile enthält $n$ ganze Zahlen $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), wobei $v_i$ das Fassungsvermögen des $i$-ten Eimers ist.

Die dritte Zeile enthält $n$ ganze Zahlen $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), wobei $l_i$ die Leckrate des $i$-ten Eimers ist.

Die vierte Zeile enthält eine ganze Zahl $q$ ($1 \le q \le 2 \times 10^5$), die die Anzahl der Fragen angibt.

Die fünfte Zeile enthält $q$ ganze Zahlen $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), wobei $t_i$ das Zeitlimit für die $i$-te Anfrage ist.

Es wird garantiert, dass weder die Summe von $n$ noch die Summe von $q$ über alle Testfälle $2 \times 10^5$ überschreitet.

Ausgabe

Gib für jeden Testfall eine Zeile mit $q$ durch Leerzeichen getrennten ganzen Zahlen aus, wobei die $i$-te ganze Zahl das maximale insgesamt verbleibende Wasservolumen nach $t_i$ Sekunden ist.

Beispiele

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.