Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Trên web đọc dữ liệu từ bàn phím (stdin) và in ra màn hình (stdout).

Bài 2 (6 điểm): HỘP QUÀ

Có ~N~ hộp quà được đánh số từ ~1~ đến ~N~, hộp quà thứ ~i~ ~(i = 1, 2, \ldots, N)~ có giá trị thẩm mỹ là ~m_i~. Nếu xếp lần lượt các hộp quà theo số thứ tự ~1, 2, \ldots, N~ thì giá trị thẩm mỹ của ~N~ hộp quà là

~m_1 + m_2 + \ldots + m_N + \max(0, m_2 - m_1) + \max(0, m_3 - m_2) + \ldots + \max(0, m_N - m_{N-1})~.

Học sinh An được giao nhiệm vụ là tìm ra cách xếp ~N~ hộp quà sao cho giá trị thẩm mỹ của ~N~ hộp quà là lớn nhất.

Yêu cầu: Cho ~N~ và ~m_i~, ~i = 1, 2, \ldots, N~. Xác định giá trị thẩm mỹ lớn nhất của ~N~ hộp quà.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 10^5)~.
• Dòng thứ 2 chứa ~N~ số nguyên ~m_1, m_2, \ldots, m_N~ ~(1 \le m_i \le 10000)~. Các số ghi cách nhau một dấu cách.

Kết quả

• Đưa ra giá trị thẩm mỹ lớn nhất của ~N~ hộp quà.

Giới hạn

• ~1 \le N \le 10^5~, ~1 \le m_i \le 10000~.

Sample Input 1

5
5 3 1 7 10

Sample Output 1

39

Giải thích

Ta được phép xếp lại thứ tự 5 hộp quà ~\{5, 3, 1, 7, 10\}~. Nếu xếp thành ~1, 10, 3, 7, 5~ thì giá trị thẩm mỹ là

~(1 + 10 + 3 + 7 + 5) + \max(0, 9) + \max(0, -7) + \max(0, 4) + \max(0, -2) = 26 + 9 + 0 + 4 + 0 = 39~

và không có cách xếp nào cho kết quả lớn hơn, nên đáp án là 39.