408549: GYM103185 F Fascinating Partitions

A subarray of an array is a contiguous portion of the array. A partition of an array into subarrays is a collection of subarrays that cover all the array without overlaps (each element in the array belongs to exactly one subarray). For instance, if $$$A=[3,1,4,1,5]$$$ is an array, $$$[3,1,4]$$$ and $$$[1,5]$$$ form a partition of $$$A$$$ into subarrays, while $$$[3,4,5]$$$ is not a subarray of $$$A$$$.

Given an integer array and a partition of the array into non-empty subarrays, we define the cost of each subarray as its maximum element, and the cost of the whole partition as the sum of the costs of the subarrays.

As an example, consider the array $$$[3,5,7,1,2,4]$$$. The partition formed by the subarrays $$$[3,5]$$$, $$$[7]$$$ and $$$[1,2,4]$$$ has cost $$$5 + 7 + 4 = 16$$$, while the partition formed by the subarrays $$$[3]$$$, $$$[5,7,1]$$$ and $$$[2,4]$$$ has cost $$$3 + 7 + 4 = 14$$$. Both partitions are formed by $$$k=3$$$ subarrays, but they have different costs. Other partitions may have different costs.

Given an array $$$A$$$ of $$$N$$$ integers, and an integer $$$k$$$ such that $$$1 \le k \le N$$$, consider the set $$$P(A,k)$$$ containing all the partitions of $$$A$$$ into $$$k$$$ non-empty subarrays. Can you compute the minimum cost over $$$P(A,k)$$$? Can you also compute the maximum cost? For each possible $$$k$$$? Okay, go ahead then.

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 8000$$$), the number of elements in the array $$$A$$$. The second line contains $$$N$$$ integers $$${A_1}, {A_2}, \ldots, {A_N}$$$ ($$$1 \leq A_i \leq 10^9$$$ for $$${i}={1}, {2}, \ldots, {N}$$$) representing the array.

Output $$$N$$$ lines, such that the $$$k$$$-th line contains two integers indicating respectively the minimum and maximum costs over $$$P(A,k)$$$.

6
3 5 7 1 2 4

7 7
10 12
12 16
14 19
17 21
22 22

4
1 1 1 1

1 1
2 2
3 3
4 4