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.