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

For Testdata: 0 ~ 0, Score: 11
For Testdata: 1 ~ 1, Score: 11
For Testdata: 2 ~ 2, Score: 11
For Testdata: 3 ~ 3, Score: 11
For Testdata: 4 ~ 4, Score: 11
For Testdata: 5 ~ 5, Score: 11
For Testdata: 6 ~ 6, Score: 11
For Testdata: 7 ~ 7, Score: 11
For Testdata: 8 ~ 8, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144