Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 難易度: [表示] ハック可能 ✓
統計

Mr. Ant Tenna의 TV 타임에 오신 것을 환영합니다! 이번 라운드에서는 $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.