No.1391 ±1 Abs Sum
タグ : / 解いたユーザー数 78
作問者 :
chineristAC
/ テスター :
eSeF
Problem Statement
First, you are given integers $N,\ K$ and a monotonically non-decreasing integer sequence $A=(A_1,\ A_2,\ \dots\ A_N)$ of length $N$.
For an integer sequence $B=(B_1,\ B_2,\ \dots\ B_N)$ of length $N$, define the function $f_B(x)$ as follows.
\begin{align} \displaystyle f_B(x) = \sum_{i=1}^{N}B_i \left|x-A_i \right| \end{align}For every integer sequence $B$ satisfying the following conditions, consider the minimum value of $f_B(x)$ over $A_1 \leq x \leq A_N$, and find the smallest among these values.
Conditions- $|B_i|=1$ holds for $i=1,\ 2,\ \dots\ N$
- Among $i=1,\ 2,\ \dots\ N$, there are exactly $K$ indices for which $B_i=1$ holds
($21:30$ Corrected "monotonically increasing integer sequence" to "monotonically non-decreasing integer sequence")
Input
$N\ K$ $A_1\ A_2\ \dots\ A_N$
- $1\leq N \leq 2\times 10^5$
- $0\leq K \leq N$
- $-10^9 \leq A_i \leq 10^9\ (1\le i \le N)$
- $A_i \leq A_{i+1}\ (1\le i \le N-1)$
- All input values are integers
Output
Output the answer.
Print a newline at the end.
Sample
Sample 1
Input
4 2 -10 -9 2 6
Output
-27
For example, if $B=(1,\ 1,\ -1,\ -1)$, then $f_B(x)$ attains its minimum value $-27$ at $x=-10$. No $B$ gives a minimum value smaller than this, so the answer is $-27$.
Sample 2
Input
4 0 -7 -2 2 4
Output
-25
Sample 3
Input
15 8 -99 -99 -94 -90 -85 -52 -47 -30 -19 6 12 14 28 45 100
Output
-683
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。