No.59 鉄道の旅

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 101
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm

3 ProblemId : 98 / 出題時の順位表

問題文

列車が出発駅から終点駅まで向かう。
その間に中間駅がN個ある。
列車は必ずすべての中間駅に停車する。
列車は出発駅では荷物を1つも積んでいない。
各中間駅では荷物を1つ積むか降ろすことが決まっている。
荷物には重さWが設定されている。
各中間駅では積むか降ろす荷物の重さが指定される。
・\(W\)が正の数の場合は、重さ\(|W|\)の荷物を詰む。
・\(W\)が負の数の場合は、重さ\(|W|\)の荷物を降ろす。

ここでひとつ変わったルールがある。

・荷物を積むまえにすでにその荷物の重さ以上の荷物がK個以上列車に積まれている場合にはその荷物を積めない。

この変わったルールのために荷物を積めない場合がある。
ルールに反しなければ必ず荷物を積む。

また、荷物を降ろす場合に指定した重さの荷物が積まれていない場合も考えられる。
この場合は指定された荷物が無いのだから荷物を降ろす必要は無い。
もし指定された重さの荷物があれば必ず1つ降ろす。
最終的に何個の荷物を最終駅まで運ぶことになるだろうか?

入力

\(N\,K\)
\(W_1\)
\(W_2\)
\(\dots\)
\(W_n\)

中間駅の数\(N\)とルールに関する値\(K\)が与えられる。
\((1 \le N \le 100000)\) (\(N\)は正の整数)
\((1 \le K \le 100000)\) (\(K\)は正の整数)
i番目に到着する中間駅の荷物の重さ\(W_i\)が順にN行で与えられる。
\(-1000000 \le W_i < 0、0< W_i \le 1000000\) (\(W_i\)は0で無い整数)
重さが負の値の場合は荷物を降ろすことを表すものとする。

出力

最終駅の時点で積まれている荷物の数を1行で出力せよ。
最後に改行を忘れずに。

サンプル

サンプル1
入力
3 2
3
3
2
出力
2

中間駅が3つある。
最初の2つの駅で重さ3の荷物を1つずつ積んだ。
3つめの駅で重さ2の荷物を1つ積みたい。
しかし、すでに重さ2以上の荷物が2つある。
ルールによりこの重さ2の荷物は積めない。
よって最終的に2個の荷物が残る。

サンプル2
入力
3 2
3
-3
2
出力
1

中間駅が3つある。
1つめの駅で重さ3の荷物を積む。
2つめの駅で重さ3の荷物を降ろす。
3つめの駅で重さ2の荷物を積むことができる。
よって最終的に1個の荷物が残る。

サンプル3
入力
5 1
5
-6
6
5
7
出力
3

中間駅が5つある。
1つめの駅で重さ5の荷物を積む。
2つめの駅では重さ6の荷物が無いので荷物を降ろさない。
3つめの駅で重さ6の荷物を積む。
4つめの駅ではすでに重さ5以上の荷物が1つ以上あるので重さ5の荷物を積めない。
5つめの駅では重さ7の荷物を積む。
よって最終的に3つの荷物が残る。

サンプル4
入力
57 8 
697
-764
-97
-58
337
-216
-827
399
-764
753
-764
764
-307
-30
-137
764
-463
-124
-815
816
546
-487
764
-43
31
162
-189
-64
-473
-884
172
546
985
901
-319
-718
-495
764
546
172
425
-816
-645
135
128
-553
764
-409
-162
276
-262
770
-162
904
337
764
-816
出力
15

提出ページヘ