Universal Cup Judging System

Universal Cup

时间限制: 7.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

題目描述

Helloooo! Can you hear me?

俾定一個長度為 $N$ 嘅序列 $A = (A_1, A_2, \dots, A_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$。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1534EditorialOpen题解jianglyView

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.