{"problem":{"name":"『STA - R1』Crossnews","description":{"content":"定义两个序列 $\\{a_n\\}$，$\\{b_n\\}$ 的联合权值为 $$\\operatorname{unval}(a,b)=\\sum_{i=1}^nb_i(b_i-a_i)$$ 现给定一个序列 $\\{a_n\\}$，求满足 $\\operatorname{unval}(a,b)$ 最小的单调不减序列 $\\{b\\}$，只需输出 $\\operatorname{unval}(a,b)$ 的值即可。 注意","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8879"},"statements":[{"statement_type":"Markdown","content":"定义两个序列 $\\{a_n\\}$，$\\{b_n\\}$ 的联合权值为\n$$\\operatorname{unval}(a,b)=\\sum_{i=1}^nb_i(b_i-a_i)$$\n\n现给定一个序列 $\\{a_n\\}$，求满足 $\\operatorname{unval}(a,b)$ 最小的单调不减序列 $\\{b\\}$，只需输出 $\\operatorname{unval}(a,b)$ 的值即可。\n\n注意，$\\{b\\}$ 中的元素不一定要为整数。\n\n## Input\n\n第一行一个正整数 $n$。\n\n第二行 $n$ 个整数表示 $a_i$。\n\n## Output\n\n一行一个答案。\n\n[samples]\n\n## Background\n\nInformational problems make us better.\n\n## Note\n\n提示：如果你不会做这道题，可以问问 [APJifengc](/user/279652)。\n***\n\n样例 1 解释：使得联合权值取到最小值的 $\\{b\\}$ 为 `0.5 1 1.5 2 2.5`。\n\n***\n数据范围和约定：\n$$\n\\newcommand{\\arraystretch}{1.5}\n\\begin{array}{c|c|c|c}\\hline\\hline\n\\textbf{Subtask} & \\bm{n}\\le & \\textbf{分值} & \\textbf{特殊性质}\\\\\\hline\n\\textsf{1} & 100 & 10 & \\textbf{无} \\\\\\hline\n\\textsf{2} & 10^6 & 5 & \\{a\\}\\textbf{ 全部相等} \\\\\\hline\n\\textsf{3} & 10^6 & 5 & \\{a\\}\\textbf{ 单调不减} \\\\\\hline\n\\textsf{4} & 10^4 & 30 & \\textbf{无} \\\\\\hline\n\\textsf{5} & 10^6 & 50 & \\textbf{无}\n\\\\\\hline\\hline\n\\end{array}\n$$\n\n对于全部数据，有 $1\\le n\\le 10^6$，$|a_i|\\le 10^3$。\n\n***\n\n评分规则：\n\n本题使用 Special Judge，如果你的答案是 $pans$，标准答案是 $cans$，则你将获得\n$$\\min\\Bigg\\{100,\\Bigg\\lfloor\\dfrac{0.1}{\\min\\Big\\{|pans-cans|,\\Big|\\dfrac{|pans-cans|}{cans}\\Big|\\Big\\}}\\Bigg\\rfloor\\Bigg\\}$$\n分。\n\n**每个 Subtask 内捆绑测试**。即取 Subtask 内得分最小的作为 Subtask 得分。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8879","tags":["Special Judge","单调栈","保序回归"],"sample_group":[["5\n1 2 3 4 5","-13.7500000"],["10\n1000 1 2 8 9 5 4 1000 -40 1000","-403015.7500000"]],"created_at":"2026-03-03 11:09:25"}}