Cân Bằng Vi Khuẩn

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bác John quản lý $N$ mảnh đất cỏ, mỗi mảnh có mức vi khuẩn chênh lệch so với mức khỏe mạnh là $a_{i}$ (dương nghĩa là thừa, âm nghĩa là thiếu).

Bác John có hai loại thuốc xịt. Mỗi lần xịt, bác chọn một vị trí $h$ ( $1 \leq h \leq N$ ) và loại thuốc (thêm hoặc bớt vi khuẩn):

Thuốc ảnh hưởng đến các mảnh từ $h$ đến $N$ : mảnh thứ $h$ bị ảnh hưởng $1$ đơn vị, mảnh $h + 1$ bị ảnh hưởng $2$ đơn vị, ..., mảnh $N$ bị ảnh hưởng $N - h + 1$ đơn vị.
Thuốc loại 1 thêm vi khuẩn, thuốc loại 2 bớt vi khuẩn.

Hãy tìm số lần xịt thuốc tối thiểu để đưa tất cả các mảnh đất về mức vi khuẩn khỏe mạnh (mức 0).

Dòng đầu tiên: số nguyên $N$ ( $1 \leq N \leq 2 \times 10^{5}$ ).
Dòng thứ hai: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ ( $| a_{i} | \leq 10^{15}$ ) - mức chênh lệch vi khuẩn.

In một số nguyên duy nhất - số lần xịt thuốc tối thiểu.

Input	Output	Giải thích
2 -1 3	6	Cần 6 lần xịt.
5 1 3 -2 -7 5	26	Cần 26 lần xịt.

Bình luận

Không có bình luận tại thời điểm này.