1623 . 國王烏龜的接駁車

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

78.7% (37/47)

Submission's AC Ratio

44.4% (71/160)

Tags

USACO 1996-USACO

Description

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

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

然而，搭往皇宮的專車只有$K$班，而每台車重量負荷都一樣是 $M$ 公斤。

現在依序給你每隻烏龜的重量 $w_i$ ，

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

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

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

他想問你，最多能有幾隻烏龜搭上車？

Input Format

第一行包含三個數字$N, K, M$。

第二行有$N$個數字$w_i$，表示從隊伍前端到隊伍末端的烏龜重量。

$1 \leq N, K \leq 2,000$
$1 \leq M \leq 10,000,000$
$1 \leq w_i \leq 10,000$

Output Format

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

Sample Input 1

5 2 10
5 8 12 3 5

Sample Output 1

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 (VSS, 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
Submit
Back to Top