Problem 2: Bookshelf [Neal Wu / Traditional, 2012]

When Farmer John isn't milking cows, stacking haybales, lining up his cows,

or building fences, he enjoys sitting down with a good book. Over the

years, he has collected N books (1 <= N <= 100,000), and he wants to build

a new set of bookshelves to hold them all.

Each book i has a width W(i) and height H(i). The books need to be added

to a set of shelves in order; for example, the first shelf should contain

books 1...k for some k, the second shelf should start with book k+1, and so

on. Each shelf can have a total width of at most L (1 <= L <=1,000,000,000). The height of a shelf is equal to the height of the

tallest book on that shelf, and the height of the entire set of bookshelves

is the sum of the heights of all the individual shelves, since they are all

stacked vertically.

Please help FJ compute the minimum possible height for the entire set of

bookshelves.

PROBLEM NAME: bookshelf

Bookshelf timer 1s memory 128MB

Bookshelf 1s 128MB