fork download
copy 
  1. #include <bits/stdc++.h>
  2. // #include "bits/stdc++.h"
  3.  
  4. #ifndef bhupixb
  5.     #define var(...)
  6.     #define stl(...)
  7. #endif
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12.  
  13. #define rep(i, a, b) for (int i = a; i <= (int)b; ++i)
  14.  
  15. int w, n;
  16.  
  17. void solve() {
  18.     cin >> w >> n;
  19.     map<int,int> mp;
  20.     rep(i,1,w) {
  21.         int x;
  22.         cin >> x;
  23.         mp[x]++;
  24.     }
  25.     vector<array<int,2>> a;
  26.     for (auto it: mp) {
  27.         a.push_back({it.first, it.second});
  28.     }
  29.     int N = a.size();
  30.     const int inf = 1e15;
  31.     vector<int> dp(N, inf);
  32.     vector<int> pref_sum(N), cnt(N);
  33.     for (int i = 0; i < N; ++i) {
  34.         pref_sum[i] = a[i][0] * a[i][1];
  35.         cnt[i] = a[i][1];
  36.         if (i > 0) {
  37.             cnt[i] += cnt[i-1];
  38.             pref_sum[i] += pref_sum[i - 1];
  39.        }
  40.  
  41.     }
  42.     auto getLR = [&] (int l, int r, vector<int> &pref_sum) {
  43.         if (l > r) return 0LL;
  44.         if (!(l >= 0 and r < N)) {
  45.             var(l, r);
  46.             exit(0);
  47.         }
  48.         if (!l) {
  49.             return pref_sum[r];
  50.         }
  51.         return pref_sum[r] - pref_sum[l-1];
  52.     };
  53.     int res = 1e18;
  54.     for (int i = 0; i < N; ++i) {
  55.         int ans = 0;
  56.         {
  57.             int lo = 0, hi = i - 1;
  58.             int lastJ = i;
  59.             while (lo <= hi) {
  60.                 int mid = (lo + hi) / 2;
  61.                 int j = mid;
  62.                 int diff = a[i][0] - a[j][0];
  63.                 int cnt1 = a[j][1];
  64.                 int seedha = diff * a[j][1];
  65.                 int ulta = ((n - a[i][0]) + (a[j][0])) * cnt1;
  66.                 if (seedha <= ulta) {
  67.                     hi = mid - 1;
  68.                     lastJ = mid;
  69.                 }
  70.                 else {
  71.                     lo = mid + 1;
  72.                 }
  73.             }
  74.             if (lastJ != i) {
  75.                 int ct = getLR(lastJ, i-1, cnt);
  76.                 int sum = getLR(lastJ, i - 1, pref_sum);
  77.                 int ok = a[i][0] * ct - sum;
  78.                 ans += ok;
  79.             }
  80.             if (lastJ > 0) {
  81.                 int j = lastJ - 1;
  82.                 int ct = getLR(0, j, cnt);
  83.                 int ok = 0;
  84.                 ok += ct * (n - a[i][0]);
  85.                 ok += getLR(0, j, pref_sum);
  86.                 var(ok);
  87.                 ans += ok;
  88.             }
  89.         }
  90.         {
  91.             int lo = i + 1, hi = N - 1;
  92.             int lastJ = i;
  93.             while (lo <= hi) {
  94.                 int mid = (lo + hi) / 2;
  95.                 int j = mid;
  96.                 int diff = a[j][0] - a[i][0];
  97.                 int seedha = diff * a[j][1];
  98.                 int ulta = (n - a[j][0]) * a[j][1] + (a[i][0]) * a[j][1];
  99.                 if (seedha <= ulta) {
  100.                     lastJ = mid;
  101.                     lo = mid + 1;
  102.                 }
  103.                 else {
  104.                     hi = mid - 1;
  105.                 }
  106.             }
  107.             if (lastJ != i) {
  108.                int ct = getLR(i+1, lastJ, cnt);
  109.                int sum = getLR(i+1, lastJ, pref_sum);
  110.                int ok = sum - ct * a[i][0];
  111.                ans += ok;
  112.             }
  113.             if (lastJ < N - 1) {
  114.                 int j = lastJ + 1;
  115.                 int ct = getLR(j, N - 1, cnt);
  116.                 int sum = getLR(j, N - 1, pref_sum);
  117.                 int ok = 0;
  118.                 ok += n * ct - sum + ct * a[i][0];
  119.                 ans += ok;
  120.             }
  121.         }
  122.         res = min(ans, res);
  123.     }
  124.     cout << res << '\n';
  125. }
  126.  
  127. // #define single_test
  128.  
  129. signed main() {
  130.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  131.     int t = 1;
  132.     #ifndef single_test
  133.         cin >> t;
  134.     #endif
  135.     for (int i = 1; i <= t; ++i) {
  136.         cout << "Case #" << i << ": ";
  137.         solve();
  138.     }
  139.     return 0;
  140. }
Success #stdin #stdout 0.01s 4532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case #1: 1000000000000000000
https://ideone.com/Z1xrV2
language:
C++14 (clang 8.0)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!