| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P131SUMJ - SUM1 J - Đường dây điện thoại |
Các con bò của Farmer John đang buồn phiền về dịch vụ điện thoại nghèo nàn của chúng. Chúng muốn FJ thay thế các dây điện thoại cũ bằng cái mới, hiệu quả hơn. Hệ thống dây mới sẽ sử dụng để cài đặt N (2 <= N <= 100 000) cột điện thoại đã có, mỗi cột có chiều cao là h_i (1<= h_i <= 100). Dây mới sẽ kết nối đỉnh của hai cột liền kề nhau và sẽ chịu chi phí là C$ nhân với độ chênh lệch chiều cao của 2 cột (1 <= C <= 100). Tất nhiên những cột điện là cố định vào không thể di chuyển được.
Farmer John hình dung nếu dựng vài cột cao hơn ông ta có thể giảm chi phí. Ông ta có thể thêm một số X (m) cho một cột và mất chi phí là X^2 $.
Giúp Farmer John xác định phương án tối ưu nhất (rẻ tiền nhất) bằng cách tăng chiều cao các cột và kết nối dây cho các con bò có thể nhận được sự cải thiện dịch vụ của mình.
Input
Dòng 1: chứa 2 số nguyên N và C.
Dòng 2 đến N+1: Dòng i+1 là chiều cao của cột điện thứ i, h_i.
Output
In ra số tiền cần phải chi trả cho hệ thống đường dây điện thoại mới.
Example
Input:
5 2
2
3
5
1
4
Output:
15
Giải thích
Input:
Có 5 cột điện thoại, và chi phí là 2$ / 1m. Ban đầu các cột có chiều cao là 2, 3, 5, 1 và 4.
Output:
Cách tốt nhất là cho Farmer John nâng cao cột đầu tiên nên một đơn vị và cột thứ 4 lên 2 đơn vị để chiều cao là 3, 3, 5, 3, và 4.
Chi phí thêm chiều cao cột là: 2*2 + 1*1 = 5$. Còn hệ thống dây có chi phí là: 2$ * ( 0 + 2 + 2 + 1) = 10$, cho tổng số 15$.
| Được gửi lên bởi: | adm |
| Ngày: | 2013-07-03 |
| 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 |
hide comments
|
2013-07-24 01:52:07 Trần Vãn Dương D10CN2
Trau bo cung duoc 4.008 chay qua lau 4.3.2 AC Last edit: 2013-07-24 01:57:55 |
