1811 . 書架

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

82.2% (37/45)

Submission's AC Ratio

29.8% (61/205)

Tags

HOJ USACO 2012-USACO

Description

猥瑣的那個人有N本小黃書直立排成一列(1 <= N <= 100,000)，每本書有其高度H(i)以及寬度W(i)

但是猥瑣的那個人想用很多個寬度為 L (1 <= L <= 1,000,000,000)的書架將書本整理好
每次裝書都必須從1號書開始,2,3,...,直到k號裝在一個書架
然後下次再從k+1本開始裝,k+2,k+3,...
這些書的總寬度不能超過L
而這個書架的高度就是這些書當中最高那本的高度
那個人覺得全部的書架疊起來越矮、看起來越美觀

問最少的書架高度總和是多少？

Input Format

第 1 行有兩個用空格分開的數字，N 和 L 。

第 2 ~ N+1 行 分別代表從左到右每一本書的高度 H(i) 寬度 W(i)。(1 <= H(i) <= 1,000,000; 1 <= W(i) <= L)

Output Format

輸出一行，代表最少需要的書架高度總和。

Sample Input 1

5 10
5 7
9 2
8 5
13 2
3 8

Sample Output 1

21

Hints

你認識那個人嗎

Problem Source

HOJ

Subtasks

No. Testdata Range Score
1 0~20 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 1000 65536 262144 1
8 1000 65536 262144 1
9 1000 65536 262144 1
10 1000 65536 262144 1
11 1000 65536 262144 1
12 1000 65536 262144 1
13 1000 65536 262144 1
14 1000 65536 262144 1
15 1000 65536 262144 1
16 1000 65536 262144 1
17 1000 65536 262144 1
18 1000 65536 262144 1
19 1000 65536 262144 1
20 1000 65536 262144 1
Submit
Back to Top