Advertisement
Guest User

Untitled

a guest
Jun 17th, 2019
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define x first
  3. #define y second
  4. #define mp make_pair
  5. #define ll long long
  6. using namespace std;
  7. const int sz = 5e5;
  8. typedef pair<int,int> ii;
  9. ii box[sz+5];
  10. ll qs_height[sz+5],qs_hole[sz+5];
  11. int main()
  12. {
  13.     int n;
  14.     cin >> n;
  15.     for(int i=1;i<=n;i++) cin >> box[i].y;
  16.     for(int i=1;i<=n;i++) cin >> box[i].x;
  17.  
  18.     sort(box+1,box+n+1);
  19.     for(int i=1;i<=n;i++) {
  20.         qs_height[i]=qs_height[i-1]+box[i].y;
  21.         qs_hole[i]=qs_hole[i-1]+box[i].x;
  22.     }
  23.     pair<long long,int> ans=mp((long long) 1e18,(int) 1e9+1);
  24.     for(int i=1;i<=n;i++) {
  25.         int x = box[i].x;
  26.         auto it = lower_bound(box+1,box+n+1,mp(x,0));
  27.         int po=it-box;
  28.         long long cnt = (qs_height[po-1]+qs_hole[po-1]-((long long) x*po-x));
  29.         long long cnt2 = qs_hole[n]-qs_hole[po]-((long long) x*(n-po));
  30.         ans=min(ans,mp(cnt+cnt2,x));
  31.     }
  32.  
  33.     cout << ans.y << " " << ans.x;
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement