Chia kẹo chênh lệch nhỏ nhất

General
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Có $N$ gói kẹo, gói thứ $i$ có $A_i$ viên kẹo. Bạn muốn chia $N$ gói kẹo này thành hai phần (mỗi phần có thể có $0$ hoặc nhiều gói, không được tách lẻ gói) sao cho độ chênh lệch tuyệt đối giữa tổng số kẹo của hai phần là nhỏ nhất có thể.

Hãy tìm độ chênh lệch nhỏ nhất đó.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$ ($1 \le N \le 500$).
  • Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 1000$).
Dữ liệu ra

Một số nguyên duy nhất là độ chênh lệch nhỏ nhất.

Ví dụ
Input Output
4<br>1 6 11 5 1
Giới hạn
  • $1 \le N \le 500$
  • $\sum A_i \le 10^5$
Draft saved