[HSG_HD_24] Chia phần

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python

Cho dãy số nguyên ~a_1, a_2, ..., a_n~. Chia dãy này thành ~2~ phần:

  • Phần thứ nhất gồm các số ~a_1, a_2, ..., a_k~ ~(1 \le k < n )~.
  • Phần thứ hai gồm các số còn lại.

Yêu cầu

Gọi ~T_1~ và ~T_2~ lần lượt là tổng các số của phần thứ nhất và phần thứ hai. Tìm giá trị nhỏ nhất của ~|T_1 - T_2|~.

Dữ liệu đầu vào

Gồm hai dòng:

  • Dòng đầu tiên chứa số nguyên dương ~n~ ~(2 \le n \le 10^6)~.
  • Dòng thứ hai chứa các số nguyên ~a_1, a_2, ..., a_n~ ~(|a_i| \le 10^9\ \forall\ i = 1, 2, ..., n)~ cách nhau bằng dấu trống.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là giá trị nhỏ nhất của ~|T_1 - T_2|~.

Ràng buộc dữ liệu

  • 75% số test kiểm tra ứng với 75% số điểm của bài có ~n \le 5000~.
  • 25% số test còn lại ứng với 25% số điểm của bài có ~n > 5000~.

Ví dụ

Ví dụ 1
INPUT
5
1 2 3 4 5
OUTPUT
3

Bình luận

Hãy đọc nội quy trước khi bình luận.