Universal Cup Judging System

Universal Cup

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

Chào mừng đến với chương trình TV Time của Mr. Ant Tenna! Trong vòng chơi này, bạn được cho $n$ chiếc xô, trong đó chiếc xô thứ $i$ có sức chứa tối đa là $v_i$ đơn vị thể tích nước. Khi trò chơi bắt đầu, tất cả các xô sẽ được đổ đầy nước, và nhiệm vụ của bạn là giữ lại nhiều nước nhất có thể trong $t$ giây tiếp theo. Nhưng có một điều bất ngờ: những chiếc xô này đều bị thủng! Chiếc xô thứ $i$ có tốc độ rò rỉ là $l_i$, nghĩa là mỗi giây sau khi trò chơi bắt đầu, chiếc xô thứ $i$ sẽ chảy mất $l_i$ đơn vị thể tích nước.

Trước khi trò chơi bắt đầu, bạn có thể gộp một số lượng xô bất kỳ thành một xô. Chiếc xô thu được sẽ có sức chứa bằng sức chứa lớn nhất trong các xô được gộp, và tốc độ rò rỉ bằng tốc độ rò rỉ nhỏ nhất trong các xô được gộp. Bạn có thể thực hiện việc gộp bao nhiêu lần tùy ý, nhưng phải thực hiện trước khi đổ nước vào.

Tenna đưa ra $q$ câu hỏi, trong đó câu hỏi thứ $i$ có giới hạn thời gian là $t_i$. Với mỗi $1 \le i \le q$, hãy tính tổng thể tích nước tối đa còn giữ lại được sau $t_i$ giây. Lưu ý rằng các câu hỏi là độc lập với nhau.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 5 \times 10^4$) biểu thị số lượng bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 2 \times 10^5$), biểu thị số lượng xô.

Dòng thứ hai chứa $n$ số nguyên $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), trong đó $v_i$ là sức chứa của chiếc xô thứ $i$.

Dòng thứ ba chứa $n$ số nguyên $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), trong đó $l_i$ là tốc độ rò rỉ của chiếc xô thứ $i$.

Dòng thứ tư chứa một số nguyên $q$ ($1 \le q \le 2 \times 10^5$), biểu thị số lượng câu hỏi.

Dòng thứ năm chứa $q$ số nguyên $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), trong đó $t_i$ là giới hạn thời gian cho truy vấn thứ $i$.

Dữ liệu đảm bảo cả tổng của $n$ lẫn tổng của $q$ trong tất cả các bộ dữ liệu đều không vượt quá $2 \times 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng gồm $q$ số nguyên cách nhau bởi dấu cách, trong đó số nguyên thứ $i$ là tổng thể tích nước tối đa còn giữ lại được sau $t_i$ giây.

Ví dụ

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.