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