Universal Cup Judging System

Universal Cup

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

ยินดีต้อนรับสู่รายการ TV Time ของ 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.