Submission #669404

#	Time	Username	Problem	Language	Result	Execution time	Memory
669404		erray	Uplifting Excursion (BOI22_vault)	C++17	50 / 100	726 ms	596 KiB

vault

// author: erray
#undef DEBUG 
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int M;
  long long L;
  cin >> M >> L;
  vector<long long> neg(M), pos(M);
  long long banked = 0;
  for (int i = 0; i < M; ++i) {
    cin >> neg[M - i - 1];
  }
  cin >> banked;
  for (int i = 0; i < M; ++i) {
    cin >> pos[i];
  }
  if (L < 0) {
    swap(neg, pos);
    L = -L;
  }
  const int inf = int(1e9);
  vector<int> dp(M * M + 1, -inf);
  dp[0] = 0;
  auto Push = [&](int x, long long c, int delta) {
    bool rev = false;
    if (x < 0) {
      rev = true;
      x = -x;
      reverse(dp.begin(), dp.end());
    }
    for (int r = 0; r < x; ++r) {
      deque<pair<int, int>> dq;
      for (int i = r, ps = 0; i < int(dp.size()); i += x, ++ps) {
        int push = dp[i] + (ps * -delta);
        while (!dq.empty() && dq.back().first <= push) {
          dq.pop_back();
        }
        dq.emplace_back(push, ps);
        if (ps > c) {
          int rem = ps - c - 1;
          if (dq.front().second == rem) {
            dq.pop_front();
          }
        }
        dp[i] = dq.front().first + (delta * ps);
      } 
    }
    if (rev) {
      reverse(dp.begin(), dp.end());
    }
  };

  auto Value = [&](vector<long long> x) {
    long long res = 0;
    for (int i = 0; i < M; ++i) {
      res += (i + 1) * x[i];
    }
    return res;
  };
  if (Value(pos) - Value(neg) < L) {
    swap(pos, neg);
    L = -L;
  }
  debug(L, pos, neg);
  for (int i = 0; i < M; ++i) {
    L += (i + 1) * neg[i]; 
    banked += neg[i];
  }
  debug(L, banked);
  vector<long long> dec(M);
  for (int i = 0; i < M; ++i) {
    dec[i] = min(pos[i], L / (i + 1));
    L -= dec[i] * (i + 1);
    pos[i] -= dec[i];  
    banked += dec[i];
  }
  debug(pos, dec, L, banked);
  assert(L >= 0);
  for (int i = 0; i < M; ++i) {
    Push(i + 1, neg[i], -1);      
  }
  for (int i = 0; i < M; ++i) {
    Push(i + 1, pos[i], +1);
  }
  for (int i = 0; i < M; ++i) {
    Push(-(i + 1), dec[i], -1);
  }
  if (dp[L] == -inf) {
    cout << "impossible\n";
  } else {
    cout << banked + dp[L] << '\n';
  }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 10 / 10
• Subtask 4-1: 10 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 10 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 10 / 10
• Subtask 6-2: 0 / 10