AtCoder Grand Contest 049
翻译中…
Problem Statement
翻译中…
Integer sequences $A, B$ and $C$, each of length $N$, are given. Snuke is happy if and only if the following condition is met.
翻译中…
- For every integer
$x$,$\sum_{1 \leq i \leq N} |A_i-x| \leq \sum_{1 \leq i \leq N} |B_i-x|$holds.
翻译中…
He decided to change at least $0$ elements of $A$ to become happy. It costs him $C_i \times (A_i-t)^2$ to change $A_i$ to $t$. Here, $t$, the value after the change, should be an integer as well.
翻译中…
Find the minimum possible sum of costs in order for Snuke to become happy.
翻译中…
Constraints
翻译中…
$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$- All values in input are integers.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N
C_1 C_2 \cdots C_N翻译中…
Output
翻译中…
Print the answer.
翻译中…
样例
Input #1
3
0 1 4
1 2 3
1 3 2
Output #1
6
After the following operations, the sum of costs is $6$.
- Change $A_1$ to $2$. This change costs $1 \times (0-2)^2=4$.
- Change $A_3$ to $3$. This change costs $2 \times (4-3)^2=2$.
After the operations, $A=(2,1,3)$ holds, which makes Snuke happy. It is impossible to achieve the goal with sum of costs less than $6$, so the answer is $6$.
Input #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
Output #2
3758
Input #3
1
0
0
1
Output #3
0
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。