Approximate Equalization

AtCoder
IDabc307_g
Time2000ms
Memory256MB
Difficulty
You are given an integer sequence of length $N$: $A=(A_1,A_2,\ldots,A_N)$. Takahashi can perform the following two operations any number of times, possibly zero, in any order. * Choose an integer $i$ such that $1\leq i\leq N-1$, and decrease $A_i$ by $1$ and increase $A_{i+1}$ by $1$. * Choose an integer $i$ such that $1\leq i\leq N-1$, and increase $A_i$ by $1$ and decrease $A_{i+1}$ by $1$. Find the minimum number of operations required to make the sequence $A$ satisfy the following condition: * $\lvert A_i-A_j\rvert\leq 1$ for any pair $(i,j)$ of integers between $1$ and $N$, inclusive. ## Constraints * $2 \leq N \leq 5000$ * $\lvert A_i \rvert \leq 10^9$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $A_1$ $A_2$ $\ldots$ $A_N$ [samples]
Samples
Input #1
3
2 7 6
Output #1
4

You can make $A$ satisfy the condition with four operations as follows.

*   Choose $i=1$, and increase $A_1$ by $1$ and decrease $A_2$ by $1$, making $A=(3,6,6)$.
*   Choose $i=1$, and increase $A_1$ by $1$ and decrease $A_2$ by $1$, making $A=(4,5,6)$.
*   Choose $i=2$, and increase $A_2$ by $1$ and decrease $A_3$ by $1$, making $A=(4,6,5)$.
*   Choose $i=1$, and increase $A_1$ by $1$ and decrease $A_2$ by $1$, making $A=(5,5,5)$.

This is the minimum number of operations required, so print $4$.
Input #2
3
-2 -5 -2
Output #2
2

You can make $A$ satisfy the condition with two operations as follows:

*   Choose $i=1$, and decrease $A_1$ by $1$ and increase $A_2$ by $1$, making $A=(-3,-4,-2)$.
*   Choose $i=2$, and increase $A_2$ by $1$ and decrease $A_3$ by $1$, making $A=(-3,-3,-3)$.

This is the minimum number of operations required, so print $2$.
Input #3
5
1 1 1 1 -7
Output #3
13

By performing the operations appropriately, with $13$ operations you can make $A=(0,0,-1,-1,-1)$, which satisfies the condition in the problem statement. It is impossible to satisfy it with $12$ or fewer operations, so print $13$.
API Response (JSON)
{
  "problem": {
    "name": "Approximate Equalization",
    "description": {
      "content": "You are given an integer sequence of length $N$: $A=(A_1,A_2,\\ldots,A_N)$. Takahashi can perform the following two operations any number of times, possibly zero, in any order. *   Choose an integer $",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc307_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an integer sequence of length $N$: $A=(A_1,A_2,\\ldots,A_N)$.\nTakahashi can perform the following two operations any number of times, possibly zero, in any order.\n\n*   Choose an integer $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments