CANDY - Chia kẹo 1

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

An và Bình là hai anh em. Ba của An sau chuyến đi công tác xa nhà trở về, mua cho An và Bình ~N~ gói kẹo, gói thứ ~i~ có ~A_i~ viên kẹo.

Để tránh việc tranh giành kẹo lẫn nhau, ba của An đã thống nhất việc chia kẹo theo cách sau:

  • Trước hết, ba của An chọn ra một số nguyên ~k~ (với ~1 ≤ k ≤ N~).
  • An sẽ được chia các gói kẹo từ ~1~ đến ~k~. Phần còn lại (các gói kẹo từ ~k + 1~ đến ~N~) sẽ được chia cho Bình.

Để tránh sự phân bua giữa hai anh em, ba của An muốn lựa chọn chỉ số ~k~ sao cho chênh lệch giữa tổng số lượng viên kẹo của hai anh em là nhỏ nhất có thể. Hãy giúp ông thực hiện điều này.

Input

  • Dòng đầu tiên gồm số nguyên ~N~ ~(2 ≤ N ≤ 200000)~ - số gói kẹo;
  • Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~ ~(1 ≤ A_i ≤ 10^9)~ - số viên kẹo trong từng gói kẹo.

Giới hạn:

  • Subtask#1 ~(50\%\text{ số điểm}): N ≤ 2000~;
  • Subtask#2 ~(50\%\text{ số điểm}):~ Không có ràng buộc gì thêm.

Output

In ra chênh lệch lượng kẹo nhỏ nhất có thể.

Sample

Input #1
5
5 1 3 2 6
Output #1
1
Input #2
6
4 5 3 6 1 2
Output #2
3
Input #3
2
100 100
Output #3
0

Hint

  • Trong ví dụ thứ nhất, nếu chọn ~k = 3~ thì tổng số kẹo An được chia là ~5 + 1 + 3 = 9~, tổng số kẹo Bình được chia là ~2 + 6 = 8~, chênh lệch lượng kẹo là ~|9 − 8| = 1~.
  • Trong ví dụ thứ hai, có hai cách chọn k tối ưu:
    • Chọn ~k = 2~. Tổng số kẹo An được chia là ~4 + 5 = 9~, tổng số kẹo Bình được chia là ~3 + 6 + 1 + 2 = 12~, chênh lệch lượng kẹo là ~|9 − 12| = 3~.
    • Chọn ~k = 3~. Tổng số kẹo An được chia là ~4 + 5 + 3 = 12~, tổng số kẹo Bình được chia là ~6 + 1 + 2 = 9~, chênh lệch lượng kẹo là ~|12 − 9| = 3~.

Problem source: Kc97ble - Free Contest


Comments

Please read the guidelines before commenting.


There are no comments at the moment.