Submission #621225

#	Time	Username	Problem	Language	Result	Execution time	Memory
621225		slime	Uplifting Excursion (BOI22_vault)	C++14	40 / 100	664 ms	223344 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;
}

vector<int> all_min_knapsacks(vector<int> v, int m) { // O(m * sqrt(sum(v))), v.size ≤ m^2
  int n = v.size();
  int freq[301];
  for(int i=1; i<=300; i++) freq[i] = 0;
  for(int x: v) freq[x]++;
  int dp[301][m+1];
  for(int i=0; i<301; i++) for(int j=1; j<=m; j++) dp[i][j] = 1e18;
  dp[0][0] = 0;
  for(int i=1; i<=300; i++) {
    if(freq[i] == 0) {
      for(int j=0; j<=m; j++) dp[i][j] = dp[i-1][j]; continue;
    }
    deque<pair<int, int> > dq[i]; // min-deque
    dq[0].push_back({0, 0});
    dp[i][0] = 0;
    for(int j=1; j<=m; j++) {
      while(dq[j % i].size() && dq[j % i].back().first > dp[i-1][j] - j / i) {
        dq[j % i].pop_back();
      }
      dq[j % i].push_back({dp[i-1][j] - j / i, j});
      while(dq[j % i].size() && dq[j % i].front().second < j - i * freq[i]) {
        dq[j % i].pop_front();
      }
      dp[i][j] = min(dp[i-1][j], dq[j % i].front().first + j / i);
    }
  }
  vector<int> res;
  for(int i=0; i<=m; i++) res.push_back((dp[300][i]> 1e16 ? -1: dp[300][i]));
  return res;
}
vector<int> all_max_knapsacks(vector<int> v, int m) { // O(m * sqrt(sum(v))), v.size ≤ m^2
  int n = v.size();
  int freq[301];
  for(int i=1; i<=300; i++) freq[i] = 0;
  for(int x: v) freq[x]++;
  int dp[301][m+1];
  for(int i=0; i<301; i++) for(int j=1; j<=m; j++) dp[i][j] = -1e18;
  dp[0][0] = 0;
  for(int i=1; i<=300; i++) {
    if(freq[i] == 0) {
      for(int j=0; j<=m; j++) dp[i][j] = dp[i-1][j]; continue;
    }
    deque<pair<int, int> > dq[i]; // min-deque
    dq[0].push_back({0, 0});
    dp[i][0] = 0;
    for(int j=1; j<=m; j++) {
      while(dq[j % i].size() && dq[j % i].back().first < dp[i-1][j] - j / i) {
        dq[j % i].pop_back();
      }
      while(dq[j % i].size() && dq[j % i].front().second < j - i * freq[i]) {
        dq[j % i].pop_front();
      }
      if(dq[j % i].empty()) dp[i][j] = dp[i-1][j];
      else dp[i][j] = max(dp[i-1][j], dq[j % i].front().first + j / i);
      dq[j % i].push_back({dp[i-1][j] - j / i, j});
    }
  }
  vector<int> res;
  for(int i=0; i<=m; i++) res.push_back((dp[300][i] < -1e16 ? -1 : dp[300][i]));
  return res;
}
void solve(int tc) {
  int m, l; cin >> m >> l;
  int a[m+1];
  for(int i=0; i<m; i++) {
    int x; cin >> x;
  }
  for(int i=0; i<=m; i++) cin >> a[i];
  int contains[m+1];
  for(int i=0; i<=m; i++) contains[i] = 0;
  int sum = 0;
  contains[0] = a[0];
  if(l < 0) {
    cout << "impossible\n"; return;
  }
  if(l == 0) {
    cout << a[0] << "\n"; return;
  }
  for(int i=1; i<=m; i++) {
    int owo = min(a[i], (l - sum) / i);
    sum += owo * i;
    contains[i] = owo;
    if(sum == l) break;
    if(owo < a[i] && sum + i > l) {
      sum += i;
      contains[i]++;
      break;
    }
  }
  if(sum < l) {
    cout << "impossible\n"; return;
  }
  if(sum == l) {
    int sm = 0;
    for(int i=0; i<=m; i++) sm += contains[i];
    cout << sm << "\n"; return;
  }
  vector<int> in, out;
  for(int i=1; i<=m; i++) {
    for(int j=0; j<min(m, contains[i]); j++) in.push_back(i);
    for(int j=0; j<min(m, a[i] - contains[i]); j++) out.push_back(i);
  }
  if(in.empty() || out.empty()) {
    cout << "impossible\n"; return;
  }
  int A = sum - l;
  int insum = 0, outsum = 0;
  for(int x: in ) insum += x;
  for(int x: out ) outsum += x;
  insum = min(insum, m*m);
  outsum = min(outsum, m*m);
  vector<int> resin = all_min_knapsacks(in, insum);
  vector<int> resout = all_max_knapsacks(out, outsum);
  /*
  for(int x: resin) cout << x << " ";
  cout << "\n";
  for(int x: resout) cout << x << " ";
  cout << "\n";
  cout << A << "\n";
  */
  int sm = 0;
  for(int i=0; i<=m; i++) sm += contains[i];
  //cout << sm << "\n";
  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;
      }
    }
  }
  //vector<int> mi = min_knapsack(in, A + x);
  //vector<int> ma = max_knapsack(out, 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 'std::vector<long long int> all_min_knapsacks(std::vector<long long int>, long long int)':
vault.cpp:75:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   75 |       for(int j=0; j<=m; j++) dp[i][j] = dp[i-1][j]; continue;
      |       ^~~
vault.cpp:75:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   75 |       for(int j=0; j<=m; j++) dp[i][j] = dp[i-1][j]; continue;
      |                                                      ^~~~~~~~
vault.cpp:66:7: warning: unused variable 'n' [-Wunused-variable]
   66 |   int n = v.size();
      |       ^
vault.cpp: In function 'std::vector<long long int> all_max_knapsacks(std::vector<long long int>, long long int)':
vault.cpp:105:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  105 |       for(int j=0; j<=m; j++) dp[i][j] = dp[i-1][j]; continue;
      |       ^~~
vault.cpp:105:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  105 |       for(int j=0; j<=m; j++) dp[i][j] = dp[i-1][j]; continue;
      |                                                      ^~~~~~~~
vault.cpp:96:7: warning: unused variable 'n' [-Wunused-variable]
   96 |   int n = v.size();
      |       ^
vault.cpp: In function 'void solve(long long int)':
vault.cpp:190: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]
  190 |   for(int x=0; x<resout.size(); x++) {
      |                ~^~~~~~~~~~~~~~
vault.cpp:191: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]
  191 |     if(resout[x] != -1 && A + x < resin.size() && resin[A + x] != -1) {
      |                           ~~~~~~^~~~~~~~~~~~~~
vault.cpp:189:7: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  189 |   int id;
      |       ^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 0 / 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