猥瑣的那個人有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
而這個書架的高度就是這些書當中最高那本的高度
那個人覺得全部的書架疊起來越矮、看起來越美觀
問最少的書架高度總和是多少?
第 1 行有兩個用空格分開的數字,N 和 L 。
第 2 ~ N+1 行 分別代表從左到右每一本書的高度 H(i) 寬度 W(i)。(1 <= H(i) <= 1,000,000; 1 <= W(i) <= L)
輸出一行,代表最少需要的書架高度總和。
你認識那個人嗎
HOJ
No. | Testdata Range | Score |
---|---|---|
1 | 0~20 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
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 | |
9 | 1000 | 65536 | 262144 | |
10 | 1000 | 65536 | 262144 | |
11 | 1000 | 65536 | 262144 | |
12 | 1000 | 65536 | 262144 | |
13 | 1000 | 65536 | 262144 | |
14 | 1000 | 65536 | 262144 | |
15 | 1000 | 65536 | 262144 | |
16 | 1000 | 65536 | 262144 | |
17 | 1000 | 65536 | 262144 | |
18 | 1000 | 65536 | 262144 | |
19 | 1000 | 65536 | 262144 | |
20 | 1000 | 65536 | 262144 |