PEG Judge - CCO17 - Rainfall Storage

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 h₁, h₂, …, h_N (1 ≤ h_i ≤ 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 h_i (1 ≤ h_i ≤ 50, 1 ≤ i ≤ N), 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.