AT_agc049_f.[AGC049F] Happy Sequence

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定长度为 $N$ 的整数序列 $A,B,C$ 。当且仅当满足以下条件时，すぬけ君会感到幸福：

对于所有整数 $x$ ，都有 $\sum_{1 \leq i \leq N} |A_i - x| \leq \sum_{1 \leq i \leq N} |B_i - x|$ 。

为了让すぬけ君幸福，你可以将 $A$ 的若干（可以为零）个元素修改为任意整数。将 $A_i$ 修改为 $t$ 的代价为 $C_i \times (A_i - t)^2$ 。修改后的值也必须是整数。

请你求出让すぬけ君幸福所需的最小总代价。

输入格式

输入以如下格式从标准输入给出：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$ $C_1$ $C_2$ $\cdots$ $C_N$

输出格式

请输出答案。

输入输出样例

输入#1
```
3
0 1 4
1 2 3
1 3 2
```
输出#1
```
6
```

输入#2

20
185 89 216 105 56 383 193 161 75 196 322 180 390 15 206 78 275 338 225 167
161 77 294 117 22 382 218 140 57 231 343 160 397 8 264 68 301 349 295 157
3 1 3 5 2 1 3 4 1 4 2 2 2 2 5 1 1 5 4 3

输出#2

输入#3
```
1
0
0
1
```
输出#3
```
0
```

说明/提示

限制条件

$1 \leq N \leq 2 \times 10^5$
$0 \leq A_i \leq 2 \times 10^5$
$0 \leq B_i \leq 2 \times 10^5$
$1 \leq C_i \leq 5$
输入均为整数。

样例解释 1

可以按如下方式操作，总代价为 $6$ ：

将 $A_1$ 修改为 $2$ ，代价为 $1 \times (0-2)^2 = 4$ 。
将 $A_3$ 修改为 $3$ ，代价为 $2 \times (4-3)^2 = 2$ 。

操作后， $A = (2,1,3)$ ，此时すぬけ君感到幸福。

无法以低于 $6$ 的总代价达成目标，因此答案为 $6$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页