『STA - R1』Crossnews

Luogu

IDLGP8879

Time1000ms

Memory128MB

DifficultyP6

Special Judge单调栈保序回归

定义两个序列 $\{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)$ 的值即可。注意，$\{b\}$ 中的元素不一定要为整数。 ## Input 第一行一个正整数 $n$。第二行 $n$ 个整数表示 $a_i$。 ## Output 一行一个答案。 [samples] ## Background Informational problems make us better. ## Note 提示：如果你不会做这道题，可以问问 [APJifengc](/user/279652)。 *** 样例 1 解释：使得联合权值取到最小值的 $\{b\}$ 为 `0.5 1 1.5 2 2.5`。 *** 数据范围和约定： $$ \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{n}\le & \textbf{分值} & \textbf{特殊性质}\\\hline \textsf{1} & 100 & 10 & \textbf{无} \\\hline \textsf{2} & 10^6 & 5 & \{a\}\textbf{ 全部相等} \\\hline \textsf{3} & 10^6 & 5 & \{a\}\textbf{ 单调不减} \\\hline \textsf{4} & 10^4 & 30 & \textbf{无} \\\hline \textsf{5} & 10^6 & 50 & \textbf{无} \\\hline\hline \end{array} $$ 对于全部数据，有 $1\le n\le 10^6$，$|a_i|\le 10^3$。 *** 评分规则：本题使用 Special Judge，如果你的答案是 $pans$，标准答案是 $cans$，则你将获得 $$\min\Bigg\{100,\Bigg\lfloor\dfrac{0.1}{\min\Big\{|pans-cans|,\Big|\dfrac{|pans-cans|}{cans}\Big|\Big\}}\Bigg\rfloor\Bigg\}$$ 分。 **每个 Subtask 内捆绑测试**。即取 Subtask 内得分最小的作为 Subtask 得分。

Samples

Input #1

5
1 2 3 4 5

Output #1

-13.7500000

Input #2

10
1000 1 2 8 9 5 4 1000 -40 1000

Output #2

-403015.7500000

API Response (JSON)

{
  "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注意...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments