DMOPC '20 Contest 3 P4 - Bob and Typography

View as PDF

Submit solution


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 N 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 K be the total number of lines and t_i be the number of letters in line i. Then a split is pretty if there exists k \in \{0, \ldots, K\} such that t_1 \ge \cdots \ge t_k and t_{k+1} \le \cdots \le t_K.

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

Over all pretty splits, please help Bob find the one with the maximum number of lines!

Constraints

Each word contains at least 1 and no more than 3000 letters.

Subtask 1 [2/15]

1 \le N \le 20

Subtask 2 [3/15]

1 \le N \le 100

Subtask 3 [3/15]

1 \le N \le 700

Subtask 4 [6/15]

1 \le N \le 5000

Subtask 5 [1/15]

1 \le N \le 30\,000

Input Specification

The first line contains N, the number of words in the phrase.
The second line contains N 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 Input

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.


Comments

There are no comments at the moment.