The first subtask can be solved using brute-force. We can generate all possible splits recursively and choose the longest pretty one.

Time complexity: ~\mathcal{O}(2^N)~

The second subtask can be solved using dynamic programming. For simplicity, let's consider purely non-increasing splits only.

Let ~dp[i][j]~ be the longest non-increasing split whose last line starts at word ~i~ and ends at word ~j~, and let ~sum(a, b)~ be the total number of letters in the words between indices ~a~ and ~b~.

To calculate ~dp[i][j]~, we have ~i-1~ choices for the first word ~k~ in the second-last line, and we want to consider only the ~k~s for which ~sum(k, i-1) \ge sum(i, j)~ (in order to maintain non-increasingness). Thus, ~dp[i][j] = 1 + \max_{\substack{1 \le k \le i - 1 \\ sum(k, i-1) \ge sum(i, j)}} \left\{ dp[k][i - 1] \right\}~. Our longest non-increasing split ending at ~j~ is then ~\max_{1 \le i \le j} \{ dp[i][j] \}~. We can find all these ~dp~ values in ~\mathcal{O}(N^4)~ total.

What about the longest pretty split? Well, we can find the longest non-decreasing split whose first line starts at word ~j+1~ simply by running the above algorithm backwards. Then we can paste the non-increasing and non-decreasing splits together to get a pretty split. Taking the longest of these pretty splits over all choices of ~j~ will give us our final answer.

Time complexity: ~\mathcal{O}(N^4)~

To solve the third subtask, we can optimize the above solution by using a prefix sum array to find each ~sum~ in ~\mathcal{O}(1)~.

Time complexity: ~\mathcal{O}(N^3)~

We can solve the fourth subtask by making further optimizations. Notice that when we iterate ~k~ from ~1~ to ~i - 1~, ~sum(k, i-1)~ decreases monotonically. Hence, for each choice of ~i~ and ~j~, there exists a "crossing point" ~p_{ij}~ such that ~sum(k, i-1) \ge sum(i, j)~ for all ~k \le p_{ij}~ and ~sum(k, i-1) < sum(i, j)~ for all ~k > p_{ij}~. We can precompute all ~p_{ij}~s using a "two pointers" method in ~\mathcal{O}(N^2)~ total. Alternatively, we can use binary search to compute them in ~\mathcal{O}(N^2 \log_2 N)~.

Our DP calculation then becomes ~dp[i][j] = 1 + \max_{1 \le k \le q_{ij}} \{ dp[k][i-1]\}~. We can compute each maximum in ~\mathcal{O}(1)~ using a prefix max array for a total time complexity of ~\mathcal{O}(N^2)~.

Time complexity: ~\mathcal{O}(N^2)~

The fastest solution is based on assuming sparsity of the DP state table.

Observe that if ~i_1 < i_2~ and ~dp[i_1][j] \ge dp[i_2][j]~, there is no need to keep the ~(i_2, j)~ state at all: any subsequent configuration on it works just as well on ~(i_1, j)~ instead. So we keep only these values (known as the Pareto optimums) in our DP table (using vectors), and transit only on these values.

This can be further optimized using the following two observations:

• By considering the ~(k, i-1) \to (i, j)~ transitions in increasing order of ~i~, we only need to check whether the new value has a higher value than the previous Pareto optimum.
• The values of the maximum DP value associated with each ~j~ is monotonically decreasing as ~j~ increases. So if we binary search for the max extent that ~(k, i-1)~ can reach, we can walk downward with a pointer until the first location where the new DP value is no longer useful.

The first optimization brings the memory down to the number of Pareto opts, and is already sufficient for passing the last batch (with runtime of about 1s). The second optimization gets the runtime down to ~\log n~ times the number of Pareto optimums as well, and does about 0.3s on the data we generated.

Time complexity: ???~\mathcal{O}(N^{1.5} \log N)~???

• If you find a case that TLEs all judge + in-contest AC codes before Lunar New Year '21 (Feb 12), rpeng will curbside deliver a cooked goose to a location within 100km driving of Highway 401 Exit 299 of your choice.
• If you prove a subquadratic runtime bound, rpeng will help you write a paper.