| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P164SUME - ROUND 4E - Bức tường đẹp |
Trước nhà của Lúi có 1 bức tường gồm có n cột kề nhau, mỗi cột có một chiều cao là hi. Một bức tường được coi là đẹp nếu ước chung của chiều các các cột trong bức tường > 1. Lúi muốn biến bức tường của mình trở lên đẹp hơn bằng các cách sau:
- Cách 1: bỏ đi 1 dãy m < n cột kề nhau liên tiếp. Với cách này, Lúi sẽ phải bỏ ra m * a chi phí.
- Cách 2: Lúi chọn 1 cột và tăng hoặc giảm chiều cao của cột lên hoặc xuống 1 đơn vị. Với cách này, Lúi sẽ phải bỏ ra b chi phí.
Lưu ý: Với cách thứ nhất chỉ có thể áp dụng 1 lần và không được xóa đi cả bức tường (xóa đi tất cả các cột). Với cách thứ 2 bạn có thể áp dụng trên nhiều cột, nhưng mỗi cột chỉ có thể áp dụng 1 lần.
Giờ bạn hãy giúp Lúi tính ra chi phí nhỏ nhất cần phải bỏ ra để được 1 bức tường đẹp.
Input
Dòng đầu gồm 3 số nguyên n, a, b (n <= 106, 0 <= a, b <= 109)
Dòng tiếp theo gồm n số nguyên biểu thị chiều cao h của từng cột (2 <= hi <= 109)
Output
In ra số nguyên duy nhất là chi phi ít nhất cần phải bỏ ra.
Example
Input:
6 2 3
5 23 27 6 5 4
Output: 9
Giải thích: bạn xóa đoạn [23, 27, 6] và tăng 4->5 vậy chi phí là 2 * 3 + 3 = 9
| Được gửi lên bởi: | adm |
| Ngày: | 2016-07-29 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
