Problem ID:
hsg12la_22_v2_4
Points:
1.3 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Author:
Problem type
Phú ông làng ~XYZ~ rất giàu có, ông có ~N~ viên kim cương, viên thứ ~i~ có giá trị ~a_{i}~ . Nhân dịp sinh nhật lần thứ ~101~ của mình, ông đem ~N~ viên kim cương này chia cho hai cô con gái sao cho số viên kim cương của cô em không nhỏ hơn của cô chị.
Phú ông cho phép cô chị được chọn trước phần của mình. Là người am hiểu về kim cương, cô chị biết rõ giá trị của từng viên nên cô chọn sao cho tổng giá trị các viên kim cương mình nhận được là lớn nhất.
Yêu cầu: Hãy cho biết tổng giá trị lớn nhất của các viên kim cương mà cô chị chọn sau khi để lại số lượng viên kim cương không nhỏ hơn của mình cho cô em.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương ~N~ ~(2 \leq N \leq 10^{6})~ là số viên kim cương.
- Dòng thứ hai chứa ~N~ số nguyên dương ~a_{1}, a_{2}, \dots, a_{N}~ ~(1 \leq a_{i} \leq 1000)~, với ~a_{i}~ là giá trị của viên kim cương thứ ~i~.
Các số trên một dòng cách nhau ít nhất một dấu cách.
Kết quả ra
- Xuất ra màn hình một số nguyên duy nhất là tổng giá trị lớn nhất của các viên kim cương mà cô chị đã chọn.
Ví dụ
Dữ liệu vào
6
2 4 1 3 3 5
Kết quả ra
12
Comments