Bedao Regular Contest 20 - Đá thủ
Xem dạng PDF
HuyAT là học sinh trường P giấu tên mới thi kỳ thi V giấu tên. Vì cay cú khi choke, anh ấy đã chơi một trò để tịnh tâm lại. Trò chơi được mô tả như sau.
Ban đầu có ~N~ chồng đá, chồng thứ ~i~ có ~A_i~ viên đá. Ở mỗi lượt đi, HuyAT có thể mua ~1~ viên đá giá ~C_1~ hoặc ~2~ viên đá với giá ~C_2~. Sau khi mua đá xong thì HuyAT sẽ đặt những viên đá mình mua vòng các chồng đá. Ở mỗi lượt, mỗi chồng đá chỉ được đặt đá vào tối đa một lần. Trò chơi kết thúc khi mọi chồng đá có cùng độ cao.
Vì tiếc tiền, HuyAT muốn dùng ít tiền nhất để hoàn thành trò chơi. Hãy giúp HuyAT nhé.
Input
Dòng đầu tiên gồm ba số nguyên ~N, C_1, C_2~ ~(1 \le N \le 10^5, 1 \le C_1, C_2 \le 10^5)~.
Dòng thứ hai gồm ~N~ số nguyên là mảng ~A~ ~(1 \le A_i \le 10^6)~.
Output
- In ra một số nguyên là số tiền tối thiểu để hoàn thành trò chơi.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| ~1~ | ~20\%~ | ~C_1 \times 2 \le C_2~ |
| ~2~ | ~20\%~ | ~C_1\le C_2~ |
| ~3~ | ~30\%~ | ~N\le 1000, A_i\le 1000~ |
| ~4~ | ~30\%~ | Không có ràng buộc gì thêm |
Sample Input 1
2 15 3
1 4
Sample Output 1
45
Sample Input 2
5 10 4
2 11 11 11 12
Sample Output 2
54
Notes
Giải thích test ví dụ:
- Ở test đầu tiên, ta mua ~3~ viên đá ở ~3~ lượt và đều đặt chúng vào chồng thứ nhất.
Bình luận
e thắc mắc chút: tại sao test 1 lại ra 45 mà ko phải 18 = 15+3 ??
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.