Advertisement
Mehulcoder

PhonePe2020D

Oct 7th, 2020 (edited)
406
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.93 KB | None | 0 0
  1. /*
  2. Author: Mehul Chaturvedi
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. using ll = long long;
  9. #define all(x) (x).begin(), (x).end()
  10. #define vll vector<long long>
  11. #define vset(v, n, val) v.clear(); v.resize(n, val)
  12. #define INF 4557430888798830399ll
  13. #define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
  14. #define repr(i, n) for (int i = n; i >= 0; i--)
  15. #define trav(a, x) for(auto& a : x)
  16.  
  17. ll n, m;
  18. vll a, b, suffa, prefb, vals;
  19.  
  20. ll get(ll changeTo) {
  21.         ll ans = 0;
  22.  
  23.         ll inda = upper_bound(all(a), changeTo) - a.begin();
  24.         ll counta = n - inda;
  25.         if (inda <= n - 1) {
  26.                 ans += (abs(counta * changeTo - suffa[inda]));
  27.         }
  28.  
  29.         ll indb = lower_bound(all(b), changeTo) - b.begin() - 1;
  30.         ll countb = indb + 1;
  31.         if (indb >= 0) {
  32.                 ans += abs(prefb[indb] - countb * changeTo);
  33.         }
  34.  
  35.         return ans;
  36. }
  37.  
  38. void solve() {
  39.         cin >> n;
  40.         vset(a, n, 0);
  41.         rep(i, n) cin >> a[i];
  42.  
  43.         cin >> m;
  44.         vset(b, m, 0);
  45.         rep(i, m) cin >> b[i];
  46.  
  47.         sort(all(a));
  48.         sort(all(b));
  49.  
  50.         rep(i, n) vals.push_back(a[i]);
  51.         rep(i, m) vals.push_back(b[i]);
  52.  
  53.         sort(all(vals));
  54.  
  55.         vset(suffa, n, 0);
  56.         vset(prefb, m, 0);
  57.  
  58.         repr(i, n - 1) {
  59.                 suffa[i] = a[i];
  60.                 if (i != n - 1) suffa[i] += suffa[i + 1];
  61.         }
  62.  
  63.  
  64.         rep(i, m) {
  65.                 prefb[i] = b[i];
  66.                 if (i != 0) prefb[i] += prefb[i - 1];
  67.         }
  68.  
  69.  
  70.         ll ans = INF;
  71.         trav(elem, vals) {
  72.                 ll cost = get(elem);
  73.                 ans = min(ans, cost);
  74.         }
  75.  
  76.         cout << ans << '\n';
  77.         return;
  78. }
  79.  
  80. int main(int argc , char ** argv) {
  81.         ios_base::sync_with_stdio(false) ;
  82.         cin.tie(NULL) ;
  83.  
  84.         ll t = 1;
  85.  
  86.         while (t--) {
  87.                 solve();
  88.         }
  89.  
  90.         return 0 ;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement