YEZAELP

TOI15: Archery

Oct 28th, 2021
565
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli N = 5e5 + 10;
  6. const lli INF = 1e18;
  7. using pl = pair <lli, lli>;
  8. lli height[N], pos[N], qs_height[N];
  9. pl ar[N];
  10.  
  11. int main(){
  12.  
  13.     lli n;
  14.     scanf("%lld", &n);
  15.  
  16.     lli min_height = INF;
  17.     for(lli i=1;i<=n;i++){
  18.         scanf("%lld", &height[i]);
  19.         min_height = min(min_height, height[i]);
  20.     }
  21.  
  22.     lli sum_pos = 0;
  23.     for(lli i=1;i<=n;i++){
  24.         scanf("%lld", &pos[i]);
  25.         sum_pos += pos[i];
  26.         ar[i] = {pos[i], height[i]};
  27.     }
  28.  
  29.     sort(ar + 1, ar + n + 1);
  30.     for(lli i=1;i<=n;i++)
  31.         qs_height[i] = qs_height[i-1] + ar[i].second;
  32.  
  33.     sort(pos + 1, pos + n + 1);
  34.  
  35.     lli ans_height = INF, ans_sum = INF, idx = 0;
  36.     for(lli i=1;i<=n;i++){
  37.         lli h = pos[i];
  38.         if(h > min_height) continue;
  39.         while(idx + 1 <= n and ar[idx + 1].first < h)
  40.             idx ++;
  41.         lli sum = sum_pos - h * n + qs_height[idx];
  42.         if(sum < ans_sum){
  43.             ans_height = h;
  44.             ans_sum = sum;
  45.         }
  46.     }
  47.  
  48.     printf("%lld %lld", ans_height, ans_sum);
  49.     return 0;
  50. }
RAW Paste Data