Kevin_Zhang

Untitled

Oct 17th, 2021 (edited)
973
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. #define pb emplace_back
  5. #define AI(i) begin(i), end(i)
  6. template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
  7. template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
  8. #ifdef KEV
  9. #define DE(args...) kout("[ " + string(#args) + " ] = ", args)
  10. void kout() { cerr << endl; }
  11. template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
  12. template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
  13. #else
  14. #define DE(...) 0
  15. #define debug(...) 0
  16. #endif
  17. // My bug list :
  18. // integer overflow
  19. // 0based, 1based forgotten
  20. // index out of bound
  21. // n, m, i, j typo
  22. // some cases are missing
  23.  
  24. const int MAX_N = 510;
  25.  
  26. int n, c, p[MAX_N], q[MAX_N], a[MAX_N], b[MAX_N], ext[MAX_N];
  27. int cnt[MAX_N];
  28.  
  29. int push(int x, int ind) {
  30.     fill(cnt, cnt + n, 0);
  31.  
  32.     int ret = 0;
  33.     while (x--) {
  34.         int pos = -1, more = -1;
  35.         for (int j = ind+1;j < n;++j) {
  36.             if (cnt[j] == c) continue;
  37.             if (chmax(more, ext[j]))
  38.                 pos = j;
  39.         }
  40.         if (pos == -1) break;
  41.         ++ret;
  42.         --ext[pos], ++cnt[pos];
  43.     }
  44.     return ret;
  45. }
  46. int solve() {
  47.     int res = 0;
  48.     for (int i = n-1;i >= 0;--i) {
  49.         int x = min(p[i], a[i]), y = min(q[i], b[i]);
  50.         res += x + y;
  51.         p[i] -= x, a[i] -= x;
  52.         q[i] -= y, b[i] -= y;
  53.         ext[i] = a[i] + b[i];
  54.         int v = push(p[i] + q[i], i);
  55.         res += v;
  56.     }
  57.     return res;
  58. }
  59. int32_t main() {
  60.     ios_base::sync_with_stdio(0), cin.tie(0);
  61.     cin >> n >> c;
  62.     for (int i = 0;i < n;++i) cin >> p[i];
  63.     for (int i = 0;i < n;++i) cin >> q[i];
  64.     for (int i = 0;i < n;++i) cin >> a[i];
  65.     for (int i = 0;i < n;++i) cin >> b[i];
  66.  
  67.     cout << solve() << '\n';
  68. }
  69.  
RAW Paste Data