fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define int ll
  5. const int N = 1e6 +100 ;
  6. vector<pair<int,int>> v(N) ; 
  7. int sa = 0 ; int sb = 0 ;
  8. int n ;
  9. int cost(int x) {
  10.     int D = 0;
  11.  
  12.     for (int i = 0; i < n; i++) {
  13.         D += max(0LL, v[i].first + v[i].second - x);
  14.     }
  15.  
  16.     int E = max(0LL, sa - x) + max(0LL, sb - x);
  17.  
  18.     return 2 * max(D, E) + 2 * x - sa - sb;
  19. }
  20.  
  21. signed main(){   
  22. 	ios_base::sync_with_stdio(false);
  23.     cin.tie(NULL);
  24.      cin >> n ; 
  25.  
  26.  
  27.     for(int i = 0 ; i < n ; i++){
  28.     	cin >> v[i].first >> v[i].second ; 
  29.     	sa += v[i].first ; 
  30.     	sb += v[i].second;
  31.     }
  32.     int l = 0 ; int r = 1e13 ; 
  33.     while( l < r){
  34.     	int m = (l + r)/2 ; 
  35.     	if(cost(m) < cost(m+1)){
  36.     		r = m ; 
  37.     	}else{
  38.     		l = m + 1 ; 
  39.     	}
  40.     }
  41.  
  42.     int ans = min(cost(l) , cost(l+1)) ; 
  43.     if(l > 0) ans = min(ans , cost(l-1)) ; 
  44.     cout << ans << endl ;
  45. }
Success #stdin #stdout 0.01s 18784KB
comments (?)
stdin
copy 
2
1 0
1 0
stdout
copy 
2
https://ideone.com/bzpN1i
language:
C++14 (gcc 8.3)
created:
1 day 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!