{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n\u003cp\u003e假设你和你的队友Mixsx将参加Namomo营。Namomo营将在连续$$$n$$$天内进行。我们将第$$$i$$$天称为第$$$i$$$天($$$1\\le i\\le n$$$)。第$$$i$$$天的费用是$$$s_i$$$。\u003c/p\u003e\n\u003cp\u003e不幸的是,Namomo营的日程安排与Mixsx的期末考试冲突。Mixsx在第$$$L$$$天到第$$$R$$$天之间每天都有期末考试。他的大学还没有公布$$$L$$$和$$$R$$$的确切值,所以我们假设满足$$$1\\le L\\le R\\le n$$$的每一对整数$$$L$$$和$$$R$$$被选中的概率是$$$1/(n(n+1)/2)$$$。他决定参加所有的考试,因此从第$$$L$$$天到第$$$R$$$天将缺席Namomo营。在这种情况下,他的\u003cspan class\u003d\"tex-font-style-it\"\u003e损失\u003c/span\u003e将是$$$\\sum_{i\u003dL}^R s_i$$$。\u003c/p\u003e\n\u003cp\u003e作为Mixsx的队友,你希望Mixsx放弃他的期末考试,回到Namomo营。在$$$L$$$和$$$R$$$公布之前,你可以准备$$$k$$$个计划。在第$$$i$$$个计划($$$1\\le i\\le k$$$)中,你每天从第$$$l_i$$$天到第$$$r_i$$$天切断他的大学电源。只要它们是满足$$$1\\le l_i\\le r_i\\le n$$$的两个整数,你可以选择$$$l_i$$$和$$$r_i$$$的值。\u003c/p\u003e\n\u003cp\u003e一旦$$$L$$$和$$$R$$$被公布,你可以选择一个满足$$$L\\le l_x\\le r_x\\le R$$$的计划$$$x$$$($$$1\\le x\\le k$$$)。然后Mixsx将在第$$$l_x$$$天到第$$$r_x$$$天每天回到Namomo营。在这种情况下,他的损失变为$$$\\sum_{i\u003dL}^R s_i-\\sum_{i\u003dl_x}^{r_x} s_i$$$。你将选择一个使Mixsx的损失最小化的计划。如果没有计划$$$x$$$满足$$$L\\le l_x\\le r_x\\le R$$$,Mixsx将正常参加他的期末考试,他的损失是$$$\\sum_{i\u003dL}^R s_i$$$。\u003c/p\u003e\n\u003cp\u003e请计算如果你选择最优的$$$k$$$个计划,Mixsx的最小可能预期损失$$$ans_k$$$。对于每一个从$$$1$$$到$$$n(n+1)/2$$$的$$$k$$$,输出$$$ans_k\\cdot n(n+1)/2$$$。\u003c/p\u003e\n\u003cp\u003e正式地,给定一个包含$$$n$$$个数字的列表$$$s_i$$$ $$$(1 \\leq i \\leq n)$$$,定义一个损失函数$$$C(L, R) \u003d \\sum_{i\u003dL}^R s_i$$$。给定一个整数$$$k$$$($$$1 \\leq k \\leq n (n + 1) / 2$$$),你应该选择$$$2k$$$个满足$$$1\\le l_i\\le r_i\\le n$$$的整数$$$l_1, \\ldots, l_k, r_1,\\ldots, r_k$$$,对于所有$$$1 \\leq i \\leq k$$$,使得\u003c/p\u003e\n\u003cp\u003e$$$$$$\\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]$$$$$$\u003c/p\u003e\n\u003cp\u003e最小化。(如果没有$$$i$$$满足$$$1\\le i\\le k$$$和$$$L \\leq l_i \\leq r_i \\leq R$$$,则$$$\\max_{1\\le i\\le k, L \\leq l_i \\leq r_i \\leq R} C(l_i, r_i)$$$定义为$$$0$$$。)对于$$$[1, n(n + 1) / 2]$$$中的每个整数$$$k$$$,输出最小化的值。\u003c/p\u003e\n"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数$$$n~(1 \\leq n \\leq 9)$$$。第二行包含$$$n$$$个用空格分隔的整数$$$s_i~(1 \\leq s_i \\leq 10^9)$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出包含$$$n (n + 1) / 2$$$个整数,每个整数占一行,表示当$$$k \u003d 1, \\ldots, n (n + 1) / 2$$$乘以$$$n (n + 1) / 2$$$时的期望值。可以证明结果总是整数。\u003c/p\u003e"}},{"title":"样例1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"样例2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n13 24\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e26\n13\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"样例3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n6 4 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e33\n21\n12\n8\n4\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注释","value":{"format":"HTML","content":"\u003cp\u003e对于第一个测试用例,我们只需要考虑$$$k \u003d 1$$$的情况。我们只能选择$$$l_1\u003dr_1\u003d1$$$。然后预期的损失是$$$C(1, 1) - C(1, 1) \u003d 0$$$,结果是$$$0 \\times 1 \\times (2) / 2 \u003d 0$$$。\u003c/p\u003e\n\u003cp\u003e对于第三个测试用例,考虑当$$$k \u003d 3$$$时的情况。我们选择$$$l_1\u003dr_1\u003d1$$$,$$$l_2\u003dr_2\u003d3$$$和$$$l_3\u003d1, r_3\u003d3$$$。预期的损失是$$$2$$$。结果是$$$2 \\times 6 \u003d 12$$$。\u003c/p\u003e"}}]}