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]}$ .

详情