Rar the Cat is sellfish and mean. Recently, he has been selling canned sardines to cats on the streets. However, his sales hasn't been going so well and he needs your help.
The sardine supplier has signed a deal with Rar the Cat so that he can only sell the sardines at a non-negative price of exactly K. If he sells 5 cans of sardines in a single transaction, he must only collect $5K from his customers in total for that transaction.
Well, that doesn't sound that hard right? Just set the sardine at a price of $K and sell to as many cats as possible at this price.
However, the king of cats has decreed that any sellers are not able to set a price. Instead, consumers are allowed to express how much they are willing to pay for the goods and the seller can only decide whether to sell the good to that consumer or not.
Being a magical cat, Rar the Cat can predict how much each cat is willing to pay before they reach their store and he has noted down that amount in chronological order based on when these cats are going to pass by their shop. (Yes, he can predict arrival timings too)
Luckily for Rar the Cat, some cats have expressed their willingness to pay negative amounts of money for the canned sardines, that is they will take the canned sardines if Rar the Cat paid them some money.
Due to this, Rar the cat has thought of a ingenious plan to group sales to multiple cats into a single transaction, so that the average amount of money he collects from selling each can of sardine is $K in the transaction.
However, he can only group cats that reach the store in consecutive order (chronological order).
For example, if Rar the Cat predicts that the amount the cats are willing to pay are: ($) 1 7 5 6 4 -1 and K = 3, he can only group the transactions in this way: 1 7 5 (6 4 -1) and only sell to the cats within the brackets as one transaction. Rar the Cat is not allowed to group in this way: (1 7 5) (6 4 -1) and exclude the striked out '7' as 1 and 5 are not consecutive to each other.
By grouping cats into multiple transactions, Rar the Cat is able to proof to the sardine supplier that he indeed sold the sardines at exactly $K.
At the end of the day, Rar the Cat wants to know the maximum number of canned sardines he can sell for the day without breaking the regulations.
You are provided with 2 integers N and K on the first line of input. N denotes the number of cats that will pass by Rar the Cat's store for the day.
N lines will follow with an integer on each line. The ith line denotes the amount that the ith cat is willing and will pay. (This amount can be negative)
The cats are numbered in chronological order of arrival at the store and it can be assumed that no cat will visit the store twice within the same day.
The amount of money each cat is willing to pay will fit into a 32-bit signed integer. Do note that the numbers are not unique.
K will also fit into a 32-bit signed integer and will always be non-negative (≥ 0)
Subtask 1 (11 points): 0 < N ≤ 20. Furthermore, it is guaranteed that the amount each cat is willing to pay will be within -1000 and 1000.
Subtask 2 (17 points): 0 < N ≤ 200
Subtask 3 (21 points): 0 < N ≤ 2,000
Subtask 4 (32 points): 0 < N ≤ 200,000, K = 0
Subtask 5 (19 points): 0 < N ≤ 200,000
Subtask 6 (0 points): Sample Testcases
This is a batch problem. Your program is supposed to input from stdin and output to stdout.
Your program is not allowed to create any intermediate files during the computation process.
6 3 1 7 5 6 4 -1
3
15 0 -1 0 -1 -1 -1 -1 -1 0 0 0 0 0 1 1 2
13
Rar the Cat can sell the sardines to the cats within the brackets:
-1 (0) -1 (-1 -1 -1 -1 0 0 0 0 0 1 1 2)
15 0 10 -1 -1 -1 -1 -1 0 0 5 0 0 0 0 -3 -2
12
Rar the Cat can sell the sardines to the cats within the brackets:
10 (-1 -1 -1 -1 -1 0 0 5 0 0 0 0) -3 -2
| Subtask | Score |
|---|---|
| 1 | 11 |
| 2 | 17 |
| 3 | 21 |
| 4 | 32 |
| 5 | 19 |
| 6 | 0 |