คำอธิบายโจทย์
Helloooo! Can you hear me?
กำหนดลำดับ $A = (A_1, A_2, \dots, A_N)$ ความยาว $N$ ที่ประกอบด้วยจำนวนเต็มที่มีค่ามากกว่าหรือเท่ากับ $-1$ โดยใช้ลำดับนี้และพารามิเตอร์ $c$ ให้ดำเนินการต่อไปนี้:
- เริ่มต้น กำหนดตัวแปร $x := 0$
- สำหรับ $i = 1, 2, \dots, N$ ให้ทำซ้ำการดำเนินการต่อไปนี้:
- ถ้า $A_i = -1$ ให้ปรับค่า $x$ เป็น $x := \max(0, x - c)$
- มิฉะนั้น ให้ปรับค่า $x$ เป็น $x := x + A_i$
จงตอบคำถาม $Q$ ข้อที่มีรูปแบบดังนี้:
- เมื่อพารามิเตอร์ $c = C_i$ จงหาค่าสูงสุดที่ $x$ มีได้ตลอดทั้งลำดับของการดำเนินการ
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัวคือ $N$ และ $Q$ ($1 \le N, Q \le 3 \times 10^5$) บรรทัดที่สองประกอบด้วยจำนวนเต็ม $N$ ตัวคือ $A_i$ ($-1 \le A_i \le 10^6$) แต่ละบรรทัดใน $Q$ บรรทัดถัดไปประกอบด้วยจำนวนเต็ม $C_i$ แทนค่าพารามิเตอร์สำหรับคำถามข้อที่ $i$ ($0 \le C_i \le 10^6$)
ข้อมูลส่งออก
พิมพ์ $Q$ บรรทัด ในบรรทัดที่ $i$ ให้พิมพ์คำตอบของคำถามข้อที่ $i$
ตัวอย่าง
ข้อมูลนำเข้า 1
20 11 50 100 50 100 0 200 -1 50 100 -1 200 -1 200 0 200 -1 200 200 -1 200 30 60 90 180 270 360 540 200 400 600 0
ข้อมูลส่งออก 1
1700 1550 1400 950 570 500 500 850 500 500 1850
หมายเหตุ
เราอธิบายคำถามข้อแรกของข้อมูลนำเข้าตัวอย่างแรกดังนี้:
- ในคำถามข้อนี้ พารามิเตอร์คือ $c = 30$
- เริ่มต้น $x = 0$
- เนื่องจาก $A_1 = 50$ ค่า $x$ จึงถูกปรับเป็น $x = 0 + 50 = 50$
- เนื่องจาก $A_2 = 100$ ค่า $x$ จึงถูกปรับเป็น $x = 50 + 100 = 150$
- ...
- เนื่องจาก $A_6 = 200$ ค่า $x$ จึงถูกปรับเป็น $x = 300 + 200 = 500$
- เนื่องจาก $A_7 = -1$ ค่า $x$ จึงถูกปรับเป็น $x = \max(0, 500 - 30) = 470$
- ...
- เนื่องจาก $A_{19} = -1$ ค่า $x$ จึงถูกปรับเป็น $x = \max(0, 1530 - 30) = 1500$
- เนื่องจาก $A_{20} = 200$ ค่า $x$ จึงถูกปรับเป็น $x = 1500 + 200 = 1700$
เมื่อรวมส่วนที่ละไว้แล้ว ค่าสูงสุดที่ $x$ มีได้ตลอดทั้งลำดับของการดำเนินการคือ $1700$