Submission #980150

#	Time	Username	Problem	Language	Result	Execution time	Memory
980150		asdfgrace	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	1517 ms	4436 KiB

vault

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) //x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

/*

(n elems) * (n copies of each elem) * (o(n) value per element) = o(n^3) states

maybe we can do optimized knapsack with o(log(n)) bit shifts per value
so there are 1e5-1e6 states
and you have to do smth exactly (n)(2n+1)(logn) updates with o(n^3) states
for (2n + 1 numbers)
for (log(n) updates per number)
for (n^3 states)
that makes n^5 without the optimization, n^4logn with
*/

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int m; long long l;
  cin >> m >> l;
  vector<int> a(2 * m + 1);
  int psum = 0, nsum = 0;
  for (int i = 0; i < 2 * m + 1; i++) {
    cin >> a[i];
    if (i < m) nsum += a[i] * (i - m);
    else if (i > m) psum += a[i] * (i - m);
  }
  pv(nsum); pv(psum);
  if (l < nsum || l > psum) {
    cout << "impossible\n";
  } else {
    vector<int> dp(psum - nsum + 1, -1);
    dp[-nsum] = 0;
    for (int i = 0; i <= m; i++) {
      pv(i);
      int cnt = a[i + m], mxbit = 0;
      if (cnt > 0) {
        mxbit = 31 - __builtin_clz(cnt);
        pv(cnt);
        pv(mxbit);
        for (int bit = 0; bit < mxbit; bit++) {
          pv(bit);
          int shift = (i << bit);
          pv(shift);
          for (int j = psum; j >= nsum; j--) {
            if (dp[j - nsum] == -1 || j + shift > psum) continue;
            pv(j);
            dp[j - nsum + shift] = max(dp[j - nsum + shift], dp[j - nsum] + (1 << bit));
          }
        }
        cnt -= (1 << mxbit) - 1; pv(cnt);
        for (int bit = 0; (1 << bit) <= cnt; bit++) {
          if ((cnt & (1 << bit))) {
            pv(bit);
            int shift = (i << bit);
            for (int j = psum; j >= nsum; j--) {
              if (dp[j - nsum] == -1 || j + shift > psum) continue;
              dp[j - nsum + shift] = max(dp[j - nsum + shift], dp[j - nsum] + (1 << bit));
            }
          }
        }
      }
      if (i == 0) continue;
      cnt = a[-i + m], mxbit = 0;
      if (cnt > 0) {
        mxbit = 31 - __builtin_clz(cnt);
        pv(cnt); pv(mxbit);
        for (int bit = 0; bit < mxbit; bit++) {
          pv(bit);
          int shift = -(i << bit);
          for (int j = nsum; j <= psum; j++) {
            if (dp[j - nsum] == -1 || j + shift < nsum) continue;
            dp[j - nsum + shift] = max(dp[j - nsum + shift], dp[j - nsum] + (1 << bit));
          }
        }
        cnt -= (1 << mxbit) - 1; pv(cnt);
        for (int bit = 0; (1 << bit) <= cnt; bit++) {
          if ((cnt & (1 << bit))) {
            pv(bit);
            int shift = -(i << bit);
            for (int j = nsum; j <= psum; j++) {
              if (dp[j - nsum] == -1 || j + shift < nsum) continue;
              dp[j - nsum + shift] = max(dp[j - nsum + shift], dp[j - nsum] + (1 << bit));
            }
          }
        }
      }
    }
    parr(dp);
    if (dp[l - nsum] == -1) {
      cout << "impossible\n";
    } else {
      cout << dp[l - nsum] << '\n';
    }
  }
}

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