407850: GYM102900 F Fountains

Suppose you and your teammate Mixsx will attend the Namomo Camp. The Namomo Camp will happen in $$$n$$$ consecutive days. We name the $$$i$$$-th day as day $$$i$$$ ($$$1\le i\le n$$$). The cost of day $$$i$$$ is $$$s_i$$$.

Unfortunately, the schedule of the Namomo Camp conflicts with Mixsx's final exams. Mixsx has final exams every day between day $$$L$$$ and day $$$R$$$. The exact value of $$$L$$$ and $$$R$$$ have not been announced by his college so we assume that every pair of integers $$$L$$$ and $$$R$$$ satisfying $$$1\le L\le R\le n$$$ will be chosen with probability $$$1/(n(n+1)/2)$$$. He decides to take all the exams and thus be absent from the Namomo Camp from day $$$L$$$ to day $$$R$$$. His loss will be $$$\sum_{i=L}^R s_i$$$ in this case.

As Mixsx's teammate, you want Mixsx to give up his final exams and come back to the Namomo Camp. You can prepare $$$k$$$ plans before $$$L$$$ and $$$R$$$ are announced. In the $$$i$$$-th plan ($$$1\le i\le k$$$), you shut the electricity off to his college every day from day $$$l_i$$$ to day $$$r_i$$$. You can choose the values of $$$l_i$$$ and $$$r_i$$$ as long as they are two integers satisfying $$$1\le l_i\le r_i\le n$$$.

Once $$$L$$$ and $$$R$$$ are announced, you can choose a plan $$$x$$$ ($$$1\le x\le k$$$) such that $$$L\le l_x\le r_x\le R$$$. Then Mixsx will come back to the Namomo Camp on every day from day $$$l_x$$$ to day $$$r_x$$$. His loss becomes $$$\sum_{i=L}^R s_i-\sum_{i=l_x}^{r_x} s_i$$$ in this case. You will choose a plan that minimizes Mixsx's loss. If no plan $$$x$$$ satisfies $$$L\le l_x\le r_x\le R$$$, Mixsx will attend his final exams normally and his loss is $$$\sum_{i=L}^R s_i$$$.

Please calculate the minimum possible expected loss $$$ans_k$$$ of Mixsx if you choose the $$$k$$$ plans optimally. Output $$$ans_k\cdot n(n+1)/2$$$ for every $$$k$$$ from $$$1$$$ to $$$n(n+1)/2$$$.

Formally, given a list of $$$n$$$ numbers $$$s_i$$$ $$$(1 \leq i \leq n)$$$, define a loss function $$$C(L, R) = \sum_{i=L}^R s_i$$$. Given an integer $$$k$$$ ($$$1 \leq k \leq n (n + 1) / 2$$$), you should select $$$2k$$$ integers $$$l_1, \ldots, l_k, r_1,\ldots, r_k$$$ satisfying $$$1\le l_i\le r_i\le n$$$ for all $$$1 \leq i \leq k$$$, such that

$$$$$$\sum_{1\leq L\leq R\leq n} \left[C(L, R) - \max_{1\le i\le k, L \leq l_i \leq r_i \leq R} C(l_i, r_i) \right]$$$$$$

is minimized. ($$$\max_{1\le i\le k, L \leq l_i \leq r_i \leq R} C(l_i, r_i)$$$ is defined as $$$0$$$ if no $$$i$$$ satisfies $$$1\le i\le k$$$ and $$$L \leq l_i \leq r_i \leq R$$$.) Output the minimized value for every integer $$$k$$$ in $$$[1, n(n + 1) / 2]$$$.

The first line contains an integer $$$n~(1 \leq n \leq 9)$$$. The second line contains $$$n$$$ space separated integers $$$s_i~(1 \leq s_i \leq 10^9)$$$.

The output contains $$$n (n + 1) / 2$$$ integers in their own lines, the expectations when $$$k = 1, \ldots, n (n + 1) / 2$$$ multiplied by $$$n (n + 1) / 2$$$. It can be shown that the results are always integers.

1
1

0

2
13 24

26
13
0

3
6 4 7

33
21
12
8
4
0

For the first test case, we only need to consider the case $$$k = 1$$$. We can only choose $$$l_1=r_1=1$$$. Then the expected loss is $$$C(1, 1) - C(1, 1) = 0$$$ and the result is $$$0 \times 1 \times (2) / 2 = 0$$$.

For the third test case, consider the case when $$$k = 3$$$. We choose $$$l_1=r_1=1$$$, $$$l_2=r_2=3$$$ and $$$l_3=1, r_3=3$$$. The expected loss is $$$2$$$. And the result is $$$2 \times 6 = 12$$$.