## DMOPC '20 Contest 3 P4 - Bob and Typography

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Bob is taking a course on typography, the art of arranging words! In this course, he is given a phrase with words consisting only of English letters. He must split the phrase over one or more lines, and he cannot split the phrase in the middle of a word.

For example, he can split the quick brown fox jumps over the lazy dog over four lines like this:

the quick brown
fox jumps
over
the lazy dog

As any good typographer knows, a split is pretty if the number of letters in each line (not including spaces) form:

• a non-increasing sequence,
• a non-decreasing sequence,
• or a non-increasing then non-decreasing sequence.

More rigorously, let be the total number of lines and be the number of letters in line . Then a split is pretty if there exists such that and .

For example, the following splits are pretty:

the
quick brown
fox jumps over the lazy dog
the quick brown
fox jumps
over
the lazy dog
the quick brown fox jumps over the lazy dog

And the following split is not:

the quick
brown fox jumps
over the lazy
dog

#### Constraints

Each word contains at least and no more than letters.

#### Input Specification

The first line contains , the number of words in the phrase.
The second line contains space-separated integers, the number of letters in each word.

#### Output Specification

The number of lines in the longest possible pretty split.

#### Sample Input

9
3 5 5 3 5 4 3 4 3

#### Sample Output

6

#### Explanation for Sample Output

This input corresponds to the phrase given in the problem description. One longest pretty split for that phrase is:

the quick
brown
fox
jumps
over the
lazy dog

with 6 lines.