fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. using pii = pair<int, int>;
  8. const int N = 1e5 + 5;
  9. const int inf = 1e18;
  10. int n, c, d, a[N], b[N], ans;
  11. int tmpa[N], tmpb[N];
  12. bool check() {
  13.     int mmax = b[1], mmin;
  14.     for (int i = 1; i <= n; i++) mmax = max(mmax, b[i]);
  15.  
  16.     for (int i = 1; i <= n; i++) tmpa[i] = a[i] + mmax - b[i];
  17.     mmin = tmpa[1], mmax = tmpa[1];
  18.     for (int i = 1; i <= n; i++) {
  19.         mmin = min(mmin, tmpa[i]);
  20.         mmax = max(mmax, tmpa[i]);
  21.     }
  22.     if (mmax - (mmin + d) > c) return 0;
  23.     return 1;
  24. }
  25. int calc() {
  26.     int res = 0;
  27.  
  28.     while(1) {
  29.         bool flag = 0;
  30.         int mmax = a[1];
  31.         for (int i = 1; i <= n; i++) mmax = max(mmax, a[i]);
  32.         for (int i = 1; i <= n; i++) {
  33.             if (mmax - a[i] > c) {
  34.                 int add = (mmax - c) - a[i];
  35.                 a[i] += add;
  36.                 b[i] += add;
  37.                 res += add;
  38.                 flag = 1;
  39.             }
  40.         }
  41.  
  42.  
  43.         mmax = b[1];
  44.         for (int i = 1; i <= n; i++) mmax = max(mmax, b[i]);
  45.         for (int i = 1; i <= n; i++) {
  46.             if (mmax - b[i] > d) {
  47.                 int add = (mmax - d) - b[i];
  48.                 a[i] += add;
  49.                 b[i] += add;
  50.                 res += add;
  51.                 flag = 1;
  52.             }
  53.         }
  54.         if (!flag) break;
  55.     }
  56.     return res;
  57. }
  58. void solve() {
  59.     cin >> n >> c >> d;
  60.     for (int i = 1; i <= n; i++) cin >> a[i];
  61.     for (int i = 1; i <= n; i++) cin >> b[i];
  62.     if (!check()) return cout << "-1\n", void();
  63.  
  64.     for (int i = 1; i <= n; i++) tmpa[i] = a[i], tmpb[i] = b[i];
  65.     ans = inf;
  66.     ans = min(ans, calc());
  67.     for (int i = 1; i <= n; i++) b[i] = tmpa[i], a[i] = tmpb[i];
  68.     swap(c, d);
  69.     // for (int i = 1; i <= n; i++) cerr << a[i] << " "; cerr << "\n";
  70.     // for (int i = 1; i <= n; i++) cerr << b[i] << " "; cerr << "\n";
  71.     ans = min(ans, calc());
  72.     cout << ans << "\n";
  73. }
  74. signed main() {
  75.     cin.tie(NULL)->sync_with_stdio(false);
  76.     if(ifstream("Input.inp")) {
  77.         freopen("Input.inp", "r", stdin);
  78.         freopen("Output.out", "w", stdout);
  79.     }
  80.     int tt; cin >> tt;
  81.     while(tt--) {
  82.         solve();
  83.     }
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/c2ugIL
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!