Giá Trị Nhỏ Nhất

View as PDF



Author:
Problem type
Allowed languages
C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Pascal, Prolog, Pypy, Pypy 3, Python, Scala
Points: 1500 Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

Cho số nguyên dương \(N\) và dãy số có \(N\) số nguyên \(a_1,a_2,...,a_N\).

Ta sẽ xét dãy \(b = (b_1,b_2,...,b_N)\) và dãy \(c = (c_1,c_2,...,c_N)\) như sau:

  • Với mỗi \(1 \le i \le N\) thì \(a_i = b_i + c_i\).
  • \(b\) là dãy không giảm. Có nghĩa là \(b_i \le b_{i+1}\) với mọi \(1 \le i \le N-1\).
  • \(c\) là dãy không tăng. Có nghĩa là \(c_i \ge c_{i+1}\) với mọi \(1 \le i \le N-1\).

Yêu cầu: Bạn hãy tạo ra dãy \(b\)\(c\) thỏa mãn các điều kiện trên sao cho giá trị \(\sum_{i = 1}^{N}(∣b_i∣+∣c_i∣)\) là nhỏ nhất có thể.

Input

  • Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 2 \times 10^5)\).
  • Dòng tiếp theo chứa dãy \(a_1,a_2,...,a_N\) \((-10^9 \le a_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.

Output

  • In ra giá trị nhỏ nhất có thể của \(\sum_{i = 1}^{N}(∣b_i∣+∣c_i∣)\).

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): Có \(N \le 11\).
  • Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
3
1 -2 3
Output
10
Note
  • \(b\)\(c\) có thể là các dãy:
    • \(b = (0,0,5)\)
    • \(c = (1,-2,-2)\).
  • Ta sẽ có \(\sum_{i = 1}^{N}(∣b_i∣+∣c_i∣) = (0+1)+(0+2)+(5+2) = 10\)\(10\) là giá trị nhỏ nhất có thể. Lưu ý rằng bạn có thể tạo dãy như thế nào cũng được, miễn giá trị là nhỏ nhất đúng yêu cầu đề bài.

Comments

There are no comments at the moment.