Malinovsky239

Untitled

Sep 25th, 2012
531
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <string>
  9. #include <cmath>
  10. #include <set>
  11. #include <map>
  12.  
  13. using namespace std;
  14.  
  15. typedef long long LL;
  16. typedef long double LD;
  17.  
  18. #define pb push_back
  19. #define mp make_pair
  20. #define sz(A) (int)(A).size()
  21.  
  22. const int N = int(1e5 + 5);
  23.  
  24. LL s[N], a[N];
  25.  
  26. LL sum(LL l, LL r) {
  27.     r = min(r, LL(N - 1));
  28.     return s[r] - s[l - 1];
  29. }
  30.  
  31. int main() {
  32.     int n;
  33.     cin >> n;  
  34.  
  35.     for (int i = 0; i < n; i++)
  36.         cin >> a[i];
  37.  
  38.     sort(a, a + n);
  39.     reverse(a, a + n); 
  40.  
  41.     s[0] = a[0];
  42.     for (int i = 1; i < N; i++)
  43.         s[i] = s[i - 1] + a[i];
  44.  
  45.     int q;
  46.     cin >> q;
  47.  
  48.     LL res_1 = 0;
  49.     for (int i = 1; i < n; i++)
  50.         res_1 += a[i] * i;     
  51.  
  52.     for (int i = 0; i < q; i++) {
  53.         int k;
  54.         cin >> k;
  55.  
  56.         if (k == 1) {
  57.             cout << res_1 << " ";
  58.             continue;
  59.         }  
  60.  
  61.         LL res = 0, sz = 1;
  62.  
  63.         for (LL j = 1, t = 1; j < n; j += sz, t++) {
  64.             sz *= k;
  65.             cerr << j + sz - 1 << endl;
  66.             res += sum(j, j + sz - 1) * t;
  67.         }
  68.  
  69.         cout << res << " ";
  70.     }
  71.     cout << endl;
  72.  
  73.     return 0;
  74. }
RAW Paste Data