| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P182SUMG - ROUND 2G - Kỹ thuật vun đống |
Có n đống đá có cỡ lần lượt là a[1], a[2], .. a[n].
Trong một lần di chuyển bạn có thể lấy một đống này dồn tất cả vào đống khác. Khi thêm đống i vào đống j, cỡ của đống j tăng theo cỡ đống i hiện tại và đống i hết sạch (cỡ bằng không). Chi phí cho một lần di chuyển bằng với cỡ của đống được thêm vào.
Tuy nhiên một điều kiện đặt ra là chỉ được thêm vào một đống không quá k lần (sau đó chỉ có thể đem đống đó đi dồn vào đống khác).
Yêu cầu tìm chi phí tối thiểu để dồn tất cả các đống thành một đống với k cho trước.
Input
Dòng đầu tiên là số nguyên n – số đống đá (1 ≤ n ≤ 105).
Dòng thứ hai gồm n số nguyên là số lượng đá trong mỗi đống a[1], a[2], .. a[n] (1 ≤ a[i] ≤ 109).
Dòng thứ ba là số nguyên q – số lượng truy vấn cho k (1 ≤ q ≤ 105).
Dòng thứ tư bao gồm q số nguyên là q truy vấn (q giá trị k) – k[1], k[2] ,.. k[q] (1≤ k[i] ≤105).
Output
Một dòng duy nhất gồm q số nguyên là chi phí tối thiểu cho mỗi truy vấn k[i].
Example
Input: 5 2 3 4 1 1 2 2 3 Output: 9 8
Giải thích
Trong truy vấn k= 2 : một cách để có chi phí tối thiểu là lấy đống 4 và đống 5 dồn vào đống 2 (chi phí 2x1 = 2) được [2,5,4,0,0] lấy đống 1 dồn vào đống 3 chi phí 2 được [0,5,6,0,0], cuối cùng lấy đống 2 dồn vào đống 3 chi phí 5 và kết thúc , tổng chi phí là 2 × 1 + 2 + 5 = 9.
| Được gửi lên bởi: | adm |
| Ngày: | 2018-07-13 |
| 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 ASM64 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 |
