fork download
  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
stdin
Standard input is empty
stdout
0