fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. int n,k;
  6. ll a[100005],b[100005];
  7. ll f(ll x)
  8. {
  9.     ll s=0ll;
  10.     int i;
  11.     vector<ll>v;
  12.     for(i=0;i<n;i++)
  13.     {
  14.         ll aa=abs(a[i]-x)+b[i];
  15.         v.push_back(aa);
  16.     }
  17.     sort(v.begin(),v.end());
  18.     for(i=0;i<k;i++)
  19.     {
  20.         s+=v[i];
  21.     }
  22.     return s; 
  23. }
  24. int main()
  25. {
  26.     cin>>n>>k;
  27.     int i;
  28.     for(i=0;i<n;i++)
  29.     {
  30.         cin>>a[i]>>b[i];
  31.     }
  32.     ll ok=-1e9,ng=1e9;
  33.     while(abs(ok-ng)>1)
  34.     {
  35.         ll mi=(ok+ng)/2;
  36.         ll u1=f(mi);
  37.         ll u2=f(mi+1);
  38.         if(u1>=u2)
  39.         {
  40.             ok=mi;
  41.         }
  42.         else 
  43.         {
  44.             ng=mi;
  45.         }
  46.     }
  47.     cout<<f(ok+1)<<endl;
  48. }
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/VzVfBl
language:
C++ (gcc 8.3)
created:
5 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!