BigZero có một bể cá. Mỗi ngày đàn cá ăn hết đúng 3 gói thức ăn. Biết trước giá bán trong \(n\) ngày lần lượt là \(a_1, a_2, \dots, a_n\), mỗi ngày được mua nhiều gói với giá bán của ngày đó, thức ăn thừa có thể được dùng cho các ngày tiếp theo.
Yêu cầu: Cho số nguyên dương \(n\) và các số nguyên dương \(a_1, a_2, \dots, a_n\), trong đó \(a_i\) là giá bán một gói thức ăn trong ngày thứ \(i\) \((1 \le i \le n \le 10^6; a_i \le 10^9)\). Hãy xác định số tiền tối thiểu để mua thức ăn cho đàn cá trong \(n\) ngày.
Input
Vào từ tệp văn bản FISH.INP:
- Dòng thứ nhất chứa một số nguyên dương \(n\) \((1 \le n \le 10^6)\).
- Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) \((1 \le i \le n; a_i \le 10^9)\).
Output
Ghi ra tệp văn bản FISH.OUT một số nguyên duy nhất là số tiền tối thiểu để mua thức ăn cho đàn cá trong \(n\) ngày.
Example
Test 1
Input
3
2 3 5Output
18Note
Giải thích:
- Ví dụ 1: Kế hoạch mua thức ăn là: ngày 1 mua 9 gói với giá là 2, ngày 2, 3 không mua gói nào. Số tiền tối thiểu: \(9 \times 2 + 0 \times 3 + 0 \times 5 = 18\).
- Ví dụ 2: Kế hoạch mua thức ăn là: ngày 1 mua 3 gói với giá là 5, ngày 2 mua 3 gói với giá là 3, ngày 3 mua 3 gói với giá là 2. Số tiền tối thiểu: \(3 \times 5 + 3 \times 3 + 3 \times 2 = 30\).
- Ví dụ 3: Kế hoạch mua thức ăn là: ngày 1 mua 3 gói với giá là 5, ngày 2 mua 6 gói với giá là 2, ngày 3 không mua gói nào. Số tiền tối thiểu: \(3 \times 5 + 6 \times 2 + 0 \times 3 = 27\).
Test 2
Input
3
5 3 2Output
30Test 3
Input
3
5 2 3Output
27Scoring
- Có \(30\%\) số test ứng với \(30\%\) số điểm của bài thỏa mãn: \(a_1 \le a_2 \le \dots \le a_n\).
- Có \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thỏa mãn: \(a_1 \ge a_2 \ge \dots \ge a_n\).
- \(40\%\) số test còn lại ứng với \(40\%\) số điểm của bài không có ràng buộc gì thêm.
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.