2017 Canadian Computing Olympiad

Day 2, Problem 1 - Rainfall Storage

It was a dark and stormy night. It also rained, and rained, and rained.

Lucy wants to capture some of the rain, but she only has limited materials. She has a collection of pillars, of various heights, which she can configure to capture the rain. Each pillar is an integer height and width of 1. Once Lucy has her configuration of pillars, she has enough other siding material to enclose the front and back to allow rain to fill all the available space in between pillars. There is more than enough rain and any excess rain will overflow and get absorbed into the earth.

For example, if Lucy has pillars of height 1, 5, 2, 1, 4, she could configure them as follows (all configurations are illustrated from the side):

 *
 * *
 * *
** *
*****

Which would capture 5 units of rain (R) as follows:

 *
 *RR*
 *RR*
 **R*
*****

For this first collection of pillars (1, 5, 2, 1, 4), she could also capture 6 units of rain as follows:

 *
 *RR*
 *RR*
**RR*
*****

As another example, if the collection of pillars was (5, 1, 5, 1, 5), Lucy could capture 8 units of rain as follows:

*R*R*
*R*R*
*R*R*
*R*R*
*****

Finally, this configuration of (5, 1, 4, 1, 5) captures 9 units of rain:

*RRR*
*R*R*
*R*R*
*R*R*
*****

Lucy has N pillars (2 ≤ N ≤ 500) with heights h1, h2, …, hN (1 ≤ hi ≤ 50). She would like to know, of all possible configurations of pillars, what are all of the obtainable volumes of rainfall that she can capture using these N pillars.

Input Format

The first line contains the integer N (2 ≤ N ≤ 500) signifying the number of pillars. The next line contains the integers hi (1 ≤ hi ≤ 50, 1 ≤ iN), representing the i-th pillar height.

For 5 of the marks available, N ≤ 10.
For an additional 10 of the 25 marks available, N ≤ 50.

Output Format

On one line, output a space-separated list of all possible obtainable integer volumes of rain captured, in increasing order.

Sample Input 1

5
1 5 2 1 4

Sample Output 1

0 1 2 3 4 5 6 8

Explanation 1

This is the first given example.

Sample Input 2

5
5 1 5 1 5

Sample Output 2

0 4 8

Explanation 2

This is the second given example.

Sample Input 3

5
5 1 4 1 5

Sample Output 3

0 1 3 4 5 6 7 8 9

Explanation 3

This is the third given example.

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 3.00s
Memory Limit: 256M
Added: Aug 09, 2017

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...