No.935 U SHI TA PU NI KI A KU N LOL BE - AM
null
leafirbyProblem Statement
Null-kun is a wielder of the "U SHI TA PU NI KI A KU N LOL BE - AM".
The "U SHI TA PU NI KI A KU N LOL BE - AM" is a beam of power $K$ that flies in a straight line, and its power decreases by $1$ each time it removes $1$ $HP$. When its power reaches 0, the beam disappears.
Now, $N$ enemies or walls stand in a row. The $i$-th enemy or wall has $A_i$ HP. When its $HP$ reaches $0$, the enemy or wall is defeated, and the beam then removes the $HP$ of the next enemy or wall.
Null-kun wants to fire the beam from any position of his choice and defeat as many enemies as possible.
Since the beam consumes a lot of $MP$, he can fire it only once.
For each of the $Q$ independent queries, find the maximum number of enemies that can be defeated at once.
Input
$N$ $S$ $A_1\ A_2\ \dots \ A_N$ $Q$ $K_1 \ K_2 \ \dots \ K_Q$
$1 \le N \le 2 \times 10^3$
$1 \le A_i \le 10^{9}(1 \le i \le N)$
$1 \le Q \le 2 \times 10^3$
$1 \le K_j \le 10^{9}(1 \le j \le Q)$
$|S|=N$
Here, $|S|$ denotes the length of the string $S$.
$N,A_i,Q,K_j$ are all integers.
$S$ contains only E or W.
$S_i$ represents an enemy if it is E and a wall if it is W.
Output
For each of the $Q$ independent queries, output on one line the maximum number of enemies that can be defeated at once when the beam's power is $K_j$. Print a newline after each query.
Print a newline at the end.
Sample
Sample 1
Input
10 EEEEEEEEEE 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10
Output
1 1 2 2 2 3 3 3 3 4
When the power satisfies $1 \le k \le 2$, firing the beam from the position of the first enemy consumes $1$ power to defeat one enemy, and defeating the second requires $1+2=3$, so three enemies is the maximum, and $1$ is output.
When the power satisfies $3 \le k \le 5$, firing the beam from the position of the first enemy consumes $3$ power to defeat two enemies, and defeating the third requires $3+3=6$, so two enemies is the maximum, and $2$ is output.
When the power satisfies $6 \le k \le 9$, firing the beam from the position of the first enemy consumes $6$ power to defeat three enemies, and defeating the third requires $6+4=10$, so three enemies is the maximum, and $3$ is output.
When the power is $k = 10$, firing the beam from the position of the first enemy consumes $10$ power to defeat four enemies, and defeating the fifth requires $10+5=15$, so four enemies is the maximum, and $4$ is output.
Sample 2
Input
10 EEWWEWEEEE 1 1 1 2 3 3 2 1 2 5 5 3 21 100 1 6
Output
2 7 7 1 3
Although not shown here, note that there are also cases where no enemy can be defeated (output $0$).
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。