No.935 う し た ぷ に き あ く ん 笑 ビ - ム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 106
作問者 : nullnull / テスター : leafirbyleafirby
4 ProblemId : 3545 / 出題時の順位表
問題文最終更新日: 2019-12-07 22:56:00

問題文

nullくんは「う し た ぷ に き あ く ん 笑 ビ - 厶」の使い手です。
「う し た ぷ に き あ く ん 笑 ビ - ム」は威力$K$のビームで、一直線に飛んでいき$HP$を$1$削ると威力が$1$減少します。威力が0になるとビームは消滅します。
さて、今ここに敵または壁が一列に$N$匹(個)並んでいます。$i$番目の敵または壁は$A_i$のHPを持っています。$HP$が$0$になると敵または壁は倒され、ビームは次の敵または壁の$HP$を削ります。
このとき、nullくんは任意の場所からビームを放ちできるだけ多くの敵を倒したいです。
ビームは$MP$の消費が激しいので一度しか打てません。
この時、$Q$個の独立したクエリについて一度に倒せる敵の最大値を求めてください。

入力

$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$
ここで$|S|$は文字列$S$の長さを示す。
$N,A_i,Q,K_j$はすべて整数である。
$S$はEまたはWのみを含む。
$S_i$は、Eで敵、Wで壁を表す。

出力

$Q$個の独立したクエリについて、ビームの強さが$K_j$の時一度に倒せる敵の最大値を一行に出力してください。各クエリごとに改行して出力してください
最後に改行してください。

サンプル

サンプル1
入力
10
EEEEEEEEEE
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
出力
1
1
2
2
2
3
3
3
3
4

威力が$1 \le k \le 2$の時、一体目の位置からビームを放つと、一体を倒すのに消費する威力が$1$で、また二体目を倒すのには$1+2=3$必要なので三体で最大となり、$1$を出力する。
威力が$3 \le k \le 5$の時、一体目の位置からビームを放つと、二体を倒すのに消費する威力が$3$で、また三体目を倒すのには$3+3=6$必要なので二体で最大となり、$2$を出力する。
威力が$6 \le k \le 9$の時、一体目の位置からビームを放つと、三体を倒すのに消費する威力が$6$で、また三体目を倒すのには$6+4=10$必要なので三体で最大となり、$3$を出力する。
威力が$k = 10$の時、一体目の位置からビームを放つと、四体を倒すのに消費する威力が$10$で、また五体目を倒すのには$10+5=15$必要なので四体で最大となり、$4$を出力する。

サンプル2
入力
10
EEWWEWEEEE
1 1 1 2 3 3 2 1 2 5
5
3 21 100 1 6
出力
2
7
7
1
3

また、ここにはおいていませんが、一体も倒せないとき($0$を出力する)もあることに注意してください。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。