Universal Cup Judging System

Universal Cup

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

歡迎來到 Mr. Ant Tenna 的電視時間!在這一輪遊戲中,你會獲得 $n$ 個水桶,其中第 $i$ 個水桶的最大容量為 $v_i$ 單位的水。在遊戲開始時,所有水桶都會被裝滿水,而你的任務是在接下來的 $t$ 秒內盡可能保留最多的水。但這裡有個轉折:這些水桶都是破的!第 $i$ 個水桶的漏水速度為 $l_i$,這意味著在遊戲開始後的每一秒,第 $i$ 個水桶都會漏掉 $l_i$ 單位的水。

在遊戲開始之前,你可以將任意數量的水桶合併為一個。合併後的水桶容量等於所合併水桶中的最大容量,而漏水速度則等於所合併水桶中的最小漏水速度。你可以進行任意多次合併,但所有合併都必須在裝水之前完成。

Tenna 提出了 $q$ 個問題,其中第 $i$ 個問題的時間限制為 $t_i$。對於每個 $1 \le i \le q$,請計算在 $t_i$ 秒後可保留的最大總水量。請注意,每個問題皆彼此獨立。

輸入格式

輸入包含多組測試資料。輸入的第一行包含一個整數 $T$($1 \le T \le 5 \times 10^4$),代表測試資料的組數。對於每組測試資料:

第一行包含一個整數 $n$($1 \le n \le 2 \times 10^5$),代表水桶的數量。

第二行包含 $n$ 個整數 $v_1, v_2, \cdots, v_n$($1 \le v_i \le 4 \times 10^{13}$),其中 $v_i$ 為第 $i$ 個水桶的容量。

第三行包含 $n$ 個整數 $l_1, l_2, \cdots, l_n$($0 \le l_i \le 10^9$),其中 $l_i$ 為第 $i$ 個水桶的漏水速度。

第四行包含一個整數 $q$($1 \le q \le 2 \times 10^5$),代表問題的數量。

第五行包含 $q$ 個整數 $t_1, t_2, \cdots, t_q$($0 \le t_i \le 10^9$),其中 $t_i$ 為第 $i$ 個詢問的時間限制。

保證所有測試資料的 $n$ 總和與 $q$ 總和皆不會超過 $2 \times 10^5$。

輸出格式

對於每組測試資料,輸出一行包含 $q$ 個以空格分隔的整數,其中第 $i$ 個整數代表在 $t_i$ 秒後的最大保留總水量。

範例

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.