Submission #622631

#	Time	Username	Problem	Language	Result	Execution time	Memory
622631		slime	Uplifting Excursion (BOI22_vault)	C++14	80 / 100	214 ms	524288 KiB

vault

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { int x; cin >> x; return (ll)x; }
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
long long fib[MAXN], lucas[MAXN];
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD); 
  lucas[0] = 2;
  lucas[1] = 1;
  for(int i=2; i<MAXN; i++) lucas[i] = (lucas[i-2] + lucas[i-1]) % MOD;
  fib[0] = 0;
  fib[1] = 1;
  for(int i=2; i<MAXN; i++) fib[i] = (fib[i-2] + fib[i-1]) % MOD;
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void gay(int i) { cout << "Case #" << i << ": "; }
int csb(int l, int r, int k) { // count number of [l, r] such that i & 2^k > 0
  if(l > r) return 0;
  if(l == 0) {
    int s = r / (1ll << (k+1)); // number of complete cycles
    int t = r % (1ll << (k+1));
    int ans = s * (1ll << k);
    ans += (t >= (1ll << k) ? t - (1ll << k) + 1 : 0);
    return ans;
  }
  else return csb(0, r, k) - csb(0, l - 1, k);
}
int lis(vector<int> a) {
  int n = a.size();
  int bucket[n+1];
  for(int i=1; i<=n; i++) bucket[i] = 1e18;
  int ans = 1;
  for(int x: a) {
    auto it = lower_bound(bucket + 1, bucket +n +1, x);
    int d = distance(bucket, it);
    ans = max(ans, d);
    bucket[d] = min(bucket[d], x);
  }
  return ans;
}
const int maxm = 300;
vector<int> all_min_knapsacks(vector<int> v, int l, int r) {
  int freq[maxm * 2 + 1];
  for(int i=0; i<=maxm * 2; i++) freq[i] = 0;
  for(int x: v) freq[x + maxm]++;
  int dp[maxm * 2 + 1][r-l+2];
  for(int i=0; i<=maxm * 2; i++) for(int j=0; j<r-l+2; j++) dp[i][j] = 1e18;
  for(int i=l; i<=0; i++) {
    if(i % maxm == 0 && abs(i / maxm) <= freq[0]) {
      dp[0][i-l] = abs(i/maxm);
    }
  }
  for(int i=1; i<=maxm * 2; i++) { // real i: i-maxm
    if(freq[i] == 0) {
      for(int j=l; j<=r; j++) {
        dp[i][j-l] = dp[i-1][j-l];
      }
    }
    else if(i - maxm == 0) {
      for(int j=l; j<=r; j++) {
        dp[i][j-l] = dp[i-1][j-l]; // min knapsack: no extra added
      }
    }
    else if(i - maxm < 0) {
      int f = abs(i - maxm);
      deque<pair<int, int> > dq[f];
      for(int j=r; j>=l; j--) {
        dp[i][j-l] = dp[i-1][j-l];
        int u = (j-l) % abs(i - maxm);
        int v = (j-l) / abs(i - maxm);
        while(dq[u].size() && dq[u].back().first > dp[i-1][j-l] + v) {
          dq[u].pop_back();
        }
        dq[u].push_back({dp[i-1][j-l] + v, j});
        while(dq[u].size() && abs(j-dq[u].front().second) / abs(i-maxm) > freq[i]) {
          dq[u].pop_front();
        }
        dp[i][j-l] = min(dp[i][j-l], dq[u].front().first - v);
      }
    }
    else {
      int f = abs(i - maxm);
      deque<pair<int, int> > dq[f];
      for(int j=l; j<=r; j++) {
        dp[i][j-l] = dp[i-1][j-l];
        int u = (j-l) % abs(i - maxm);
        int v = (j-l) / abs(i - maxm);
        while(dq[u].size() && dq[u].back().first > dp[i-1][j-l] - v) {
          dq[u].pop_back();
        }
        dq[u].push_back({dp[i-1][j-l] - v, j});
        while(dq[u].size() && abs(j-dq[u].front().second) / abs(i-maxm) > freq[i]) {
          dq[u].pop_front();
        }
        dp[i][j-l] = min(dp[i][j-l], dq[u].front().first + v);
      }
    }
    /*
    for(int j=l; j<=r; j++) {
      dp[i][j-l] = dp[i-1][j-l];
      for(int k=1; k<=freq[i]; k++) {
        int res = j - k * (i - maxm);
        if(l <= res && res <= r) dp[i][j-l] = min(dp[i][j-l], dp[i-1][res-l] + k);
      }
    }
    */
  }
  vector<int> vt;
  for(int i=l; i<=r; i++) {
    if(dp[maxm * 2][i-l] > 1e16) vt.push_back(-1);
    else vt.push_back(dp[maxm * 2][i-l]);
  }
  return vt;
}
vector<int> all_max_knapsacks(vector<int> v, int l, int r) {
  int freq[maxm * 2 + 1];
  for(int i=0; i<=maxm * 2; i++) freq[i] = 0;
  for(int x: v) freq[x + maxm]++;
  int dp[maxm * 2 + 1][r-l+2];
  for(int i=0; i<=maxm * 2; i++) for(int j=0; j<r-l+2; j++) dp[i][j] = -1e18;
  for(int i=l; i<=0; i++) {
    if(i % maxm == 0 && abs(i / maxm) <= freq[0]) {
      dp[0][i-l] = abs(i/maxm);
    }
  }
  for(int i=1; i<=maxm * 2; i++) { // real i: i-maxm
    if(freq[i] == 0) {
      for(int j=l; j<=r; j++) {
        dp[i][j-l] = dp[i-1][j-l];
      }
    }
    else if(i - maxm == 0) {
      for(int j=l; j<=r; j++) {
        dp[i][j-l] = dp[i-1][j-l] + freq[i]; // max knapsack: add all
      }
    }
    else if(i - maxm < 0) {
      int f = abs(i - maxm);
      deque<pair<int, int> > dq[f];
      for(int j=r; j>=l; j--) {
        dp[i][j-l] = dp[i-1][j-l];
        int u = (j-l) % abs(i - maxm);
        int v = (j-l) / abs(i - maxm);
        while(dq[u].size() && dq[u].back().first < dp[i-1][j-l] + v) {
          dq[u].pop_back();
        }
        dq[u].push_back({dp[i-1][j-l] + v, j});
        while(dq[u].size() && abs(j-dq[u].front().second) / abs(i-maxm) > freq[i]) {
          dq[u].pop_front();
        }
        dp[i][j-l] = max(dp[i][j-l], dq[u].front().first - v);
      }
    }
    else {
      int f = abs(i - maxm);
      deque<pair<int, int> > dq[f];
      for(int j=l; j<=r; j++) {
        dp[i][j-l] = dp[i-1][j-l];
        int u = (j-l) % abs(i - maxm);
        int v = (j-l) / abs(i - maxm);
        while(dq[u].size() && dq[u].back().first < dp[i-1][j-l] - v) {
          dq[u].pop_back();
        }
        dq[u].push_back({dp[i-1][j-l] - v, j});
        while(dq[u].size() && abs(j-dq[u].front().second) / abs(i-maxm) > freq[i]) {
          dq[u].pop_front();
        }
        dp[i][j-l] = max(dp[i][j-l], dq[u].front().first + v);
      }
    }
    /*
    for(int j=l; j<=r; j++) {
      dp[i][j-l] = dp[i-1][j-l];
      for(int k=1; k<=freq[i]; k++) {
        int res = j - k * (i - maxm);
        if(l <= res && res <= r) dp[i][j-l] = min(dp[i][j-l], dp[i-1][res-l] + k);
      }
    }
    */
  }
  vector<int> vt;
  for(int i=l; i<=r; i++) {
    if(dp[maxm * 2][i-l] < -1e16) vt.push_back(-1);
    else vt.push_back(dp[maxm * 2][i-l]);
  }
  return vt;
}
void solve(int tc) {
  int m, l; cin >> m >> l;
  unordered_map<int, int> a;
  for(int i=-m; i<=m; i++) cin >> a[i];
  if(l < 0) {
    for(int i=-m; i<0; i++) swap(a[i], a[-i]);
    l = -l;
  }
  int cnt = a[0], sum = 0;
  for(int i=1; i<=m; i++) {
    int owo = (a[i] - a[-i]) * i;
    cnt += a[i] + a[-i];
    sum += owo;
  }
  if(sum == l) {
    cout << cnt << "\n"; return;
  }
  unordered_map<int, int> chosen;
  for(int i=-m; i<=m; i++) chosen[i] = a[i];
  if(sum < l) {
    for(int i=-m; i<0; i++) {
      int rem = (l - sum) / (-i);
      rem = min(rem, a[i]);
      if(sum - rem * i == l) {
        chosen[i] -= rem; 
        sum -= rem * i;
        break;
      }
      if(rem == a[i]) {
        chosen[i] = 0;
        sum -= rem * i;
      }
      else {
        rem++;
        chosen[i] -= rem;
        sum -= rem * i;
        break;
      }
    }
    if(sum < l) {
      cout << "impossible\n"; return;
    }
  }
  else {
    for(int i=m; i>0; i--) {
      int rem = (sum - l) / i;
      rem = min(rem, a[i]);
      chosen[i] -= rem;
      sum -= rem * i;
    }
  }
  if(sum == l) {
    int sm = 0;
    for(int i=-m; i<=m; i++) sm += chosen[i];
    cout << sm << "\n";
    return;
  }
  vector<int> in, out;
  for(int i=-m; i<=m; i++) {
    for(int j=0; j<min(m, chosen[i]); j++) in.push_back(i);
    for(int j=0; j<min(m, a[i] - chosen[i]); j++) out.push_back(i);
  }
  if(in.empty() || out.empty()) {
    cout << "impossible\n"; return;
  }
  int A = sum - l;
  vector<int> resin = all_min_knapsacks(in, -m*m, m*m);
  vector<int> resout = all_max_knapsacks(out, -m*m, m*m);
  int sm = 0;
  for(int i=-m; i<=m; i++) sm += chosen[i];
  int ans = -1;
  int id;
  for(int x=0; x<resout.size(); x++) {
    if(resout[x] != -1 && A + x < resin.size() && resin[A + x] != -1) {
      if(sm - resin[A + x] + resout[x] > ans) {
        ans = sm - resin[A + x] + resout[x];
        id = x;
      }
    }
  }
  cout << (ans == -1 ? "impossible" : to_string(ans)) << "\n";
} 
int32_t main() {
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// I don't know geometry.
// Teaming is unfair.

/*
5 16
0 0 0 0 0 0 0 0 3 2 1
*/ 

Compilation message (stderr)

vault.cpp: In function 'void solve(long long int)':
vault.cpp:283:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  283 |   for(int x=0; x<resout.size(); x++) {
      |                ~^~~~~~~~~~~~~~
vault.cpp:284:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  284 |     if(resout[x] != -1 && A + x < resin.size() && resin[A + x] != -1) {
      |                           ~~~~~~^~~~~~~~~~~~~~
vault.cpp:282:7: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  282 |   int id;
      |       ^~

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