TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

87.5% (21/24)

Submission's AC Ratio

44.4% (32/72)

Description

烏龜國王開放讓百姓去覲見他,舉國上下無一不期待能一睹國王的真面目。

於是,n 隻烏龜便排成一列等著搭上直達皇宮的專車。

然而,搭往皇宮的專車只有k 班,而每台車重量負荷都一樣是m 公斤。

現在依序給你每隻烏龜的重量wi,

依序每支烏龜走過來時,車長只能決定叫他立刻上車或是把他踢開,

然後當那隻烏龜上去會超過該台車的負重時那班車就會開走,下一班會立刻過來。

當然國王希望越多隻烏龜能見到他越好,

他想問你,最多能有幾隻烏龜搭上車?

Input Format

第一行包含三個數字n, k, m。

第二行有n個數字wi,表示從隊伍前端到隊伍末端的烏龜重量。

1 <= n, k <= 2,000;
1 <= m <= 10,000,000;
1 <= wi <= 10,000;

Output Format

輸出含一個數字n,表示最多能讓幾隻烏龜搭上車。

Sample Input

5 2 10
5 8 12 3 5

Sample Output

3

Hints

烏龜系列前傳。

Problem Source

原TIOJ1623 / USACO`96
Problem Setter:ATP

Subtasks

No. Testdata Range Score
1 0 11
2 1 11
3 2 11
4 3 11
5 4 11
6 5 11
7 6 11
8 7 11
9 8 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9