No.59 Railway Journey
タグ : / 解いたユーザー数 233
作問者 :
nmnmnmnmnmnmnm
Problem Statement
A train travels from the departure station to the terminal station.
There are N intermediate stations along the way.
The train always stops at every intermediate station.
The train carries no luggage at all at the departure station.
At each intermediate station, it is determined that one piece of luggage is either loaded or unloaded.
Each piece of luggage has a weight W.
At each intermediate station, the weight of the luggage to load or unload is specified.
・If \(W\) is a positive number, a piece of luggage of weight \(|W|\) is loaded.
・If \(W\) is a negative number, a piece of luggage of weight \(|W|\) is unloaded.
There is one unusual rule here.
・If, before loading a piece of luggage, K or more pieces of luggage with weight greater than or equal to that luggage's weight are already on the train, that luggage cannot be loaded.
Because of this unusual rule, there are cases where luggage cannot be loaded.
If the rule is not violated, the luggage is always loaded.
It is also possible that, when unloading, no luggage of the specified weight is on the train.
In this case, since the specified luggage does not exist, there is no need to unload anything.
If luggage of the specified weight exists, exactly one piece is always unloaded.
How many pieces of luggage will ultimately be carried to the final station?
Input
\(N\,K\) \(W_1\) \(W_2\) \(\dots\) \(W_n\)
The number of intermediate stations \(N\) and the value \(K\) related to the rule are given.
\((1 \le N \le 100000)\) (\(N\) is a positive integer)
\((1 \le K \le 100000)\) (\(K\) is a positive integer)
The luggage weights \(W_i\) at the intermediate station reached i-th are given in order over N lines.
\(-1000000 \le W_i < 0、0< W_i \le 1000000\) (\(W_i\) is a non-zero integer)
A negative weight represents unloading luggage.
Output
Output on one line the number of pieces of luggage loaded on the train at the final station.
Don't forget the newline at the end.
Sample
Sample 1
Input
3 2 3 3 2
Output
2
There are 3 intermediate stations.
At the first 2 stations, one piece of luggage of weight 3 is loaded at each.
At the 3rd station, we want to load one piece of luggage of weight 2.
However, there are already 2 pieces of luggage of weight 2 or more.
By the rule, this luggage of weight 2 cannot be loaded.
Therefore, 2 pieces of luggage remain in the end.
Sample 2
Input
3 2 3 -3 2
Output
1
There are 3 intermediate stations.
At the 1st station, a piece of luggage of weight 3 is loaded.
At the 2nd station, a piece of luggage of weight 3 is unloaded.
At the 3rd station, a piece of luggage of weight 2 can be loaded.
Therefore, 1 piece of luggage remains in the end.
Sample 3
Input
5 1 5 -6 6 5 7
Output
3
There are 5 intermediate stations.
At the 1st station, a piece of luggage of weight 5 is loaded.
At the 2nd station, there is no luggage of weight 6, so no luggage is unloaded.
At the 3rd station, a piece of luggage of weight 6 is loaded.
At the 4th station, there is already at least 1 piece of luggage of weight 5 or more, so the luggage of weight 5 cannot be loaded.
At the 5th station, a piece of luggage of weight 7 is loaded.
Therefore, 3 pieces of luggage remain in the end.
Sample 4
Input
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
Output
15
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。