INSUL - Cách nhiệt

Giới hạn

• Thời gian: 0.2s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho một dãy N viên gạch lần lượt có độ cách nhiệt là các số a ₁ .. a _N . Nếu xếp lần lượt các viên gạch theo trình tự đó thì độ cách nhiệt cả khối là a ₁ + a ₂ + ... + a _N + max(0, a ₂ - a ₁ ) + max(0, a ₃ - a ₂ ) + ... + max(0, a _N - a _{N - 1} ). Nhiệm vụ của bạn là tìm cách xếp sao cho độ cách nhiệt của cả khối là lớn nhất có thể.

Dữ liệu

• Dòng đầu ghi số nguyên dương N (0 < n ≤ 10^5).
• N dòng sau mỗi dòng ghi một số a _i ( 1 ≤ i ≤ N và 1 ≤ a _i ≤ 10000).

Kết qủa

Ghi trên một dòng kết quả cần tìm.

Ví dụ

 
Dữ liệu: 
4
5
4
1
7
Kết qủa 
24 

---

• Người up: tranhaidangfpt
• Nguồn bài: POI 2001/2002