oj.uz

Submission #619807

# Submission time Handle Problem Language Result Execution time Memory
619807 2022-08-02T16:07:28 Z slime Uplifting Excursion (BOI22_vault) C++14
10 / 100
 358 ms 524288 KB 
#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) {
  int n = v.size();
  int dp[n][m+1];
  for(int i=0; i<=m; i++) dp[0][i] = 1e18;
  dp[0][0] = 0;
  dp[0][v[0]] = 1;
  for(int i=1; i<n; i++) {
    dp[i][0] = 0;
    for(int j=1; j<=m; j++) {
      dp[i][j] = dp[i-1][j];
      if(j >= v[i]) dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]] + 1);
    }
  }
  vector<int> soln;
  for(int i=0; i<=m; i++) {
    if(dp[n-1][i] == 1e18) soln.push_back(-1);
    else soln.push_back(dp[n-1][i]);
  }
  return soln;

}
vector<int> all_max_knapsacks(vector<int> v, int m) {
  int n = v.size();
  int dp[n][m+1];
  for(int i=0; i<=m; i++) dp[0][i] = -1e18;
  dp[0][0] = 0;
  dp[0][v[0]] = 1;
  for(int i=1; i<n; i++) {
    dp[i][0] = 0;
    for(int j=1; j<=m; j++) {
      dp[i][j] = dp[i-1][j];
      if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + 1);
    }
  }
  vector<int> soln;
  for(int i=0; i<=m; i++) {
    if(dp[n-1][i] == -1e18) soln.push_back(-1);
    else soln.push_back(dp[n-1][i]);
  }
  return soln;

}
vector<int> min_knapsack(vector<int> v, int m) {
  int n = v.size();
  int dp[n][m+1];
  for(int i=0; i<=m; i++) dp[0][i] = 1e18;
  dp[0][0] = 0;
  dp[0][v[0]] = 1;
  for(int i=1; i<n; i++) {
    dp[i][0] = 0;
    for(int j=1; j<=m; j++) {
      dp[i][j] = dp[i-1][j];
      if(j >= v[i]) dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]] + 1);
    }
  }
  if(dp[n-1][m] == 1e18) return {};
  vector<int> sol;
  int j = m;
  for(int i=n-1; i>=0; i--) {
    if(i == 0) {
      if(j > 0) {
        sol.push_back(v[i]);
      }
      break;
    }
    if(j >= v[i] && dp[i][j] == dp[i-1][j-v[i]] + 1) {
      sol.push_back(v[i]);
      j -= v[i];
    }
  }
  return sol;

}
vector<int> max_knapsack(vector<int> v, int m) {
  int n = v.size();
  int dp[n][m+1];
  for(int i=0; i<=m; i++) dp[0][i] = -1e18;
  dp[0][0] = 0;
  dp[0][v[0]] = 1;
  for(int i=1; i<n; i++) {
    dp[i][0] = 0;
    for(int j=1; j<=m; j++) {
      dp[i][j] = dp[i-1][j];
      if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + 1);
    }
  }
  if(dp[n-1][m] == -1e18) return {};
  vector<int> sol;
  int j = m;
  for(int i=n-1; i>=0; i--) {
    if(i == 0) {
      if(j > 0) {
        sol.push_back(v[i]);
      }
      break;
    }
    if(j >= v[i] && dp[i][j] == dp[i-1][j-v[i]] + 1) {
      sol.push_back(v[i]);
      j -= v[i];
    }
  }
  return sol;

}
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;
  vector<int> resin = all_min_knapsacks(in, insum);
  vector<int> resout = all_max_knapsacks(out, outsum);
  int sm = 0;
  for(int i=0; i<=m; i++) sm += contains[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;
      }
    }
  }
  //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.

/*

*/

Compilation message

vault.cpp: In function 'void solve(long long int)':
vault.cpp:222: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]
  222 |   for(int x=0; x<resout.size(); x++) {
      |                ~^~~~~~~~~~~~~~
vault.cpp:223: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]
  223 |     if(resout[x] != -1 && A + x < resin.size() && resin[A + x] != -1) {
      |                           ~~~~~~^~~~~~~~~~~~~~
vault.cpp:221:7: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  221 |   int id;
      |       ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3-1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 27 ms 40660 KB Output is correct
3 Correct 8 ms 7252 KB Output is correct
4 Correct 23 ms 28624 KB Output is correct
5 Correct 46 ms 71352 KB Output is correct
6 Correct 23 ms 34264 KB Output is correct
7 Correct 9 ms 8148 KB Output is correct
8 Correct 8 ms 7508 KB Output is correct
9 Correct 10 ms 10332 KB Output is correct
10 Correct 16 ms 20564 KB Output is correct

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 27 ms 40660 KB Output is correct
3 Correct 8 ms 7252 KB Output is correct
4 Correct 23 ms 28624 KB Output is correct
5 Correct 46 ms 71352 KB Output is correct
6 Correct 23 ms 34264 KB Output is correct
7 Correct 9 ms 8148 KB Output is correct
8 Correct 8 ms 7508 KB Output is correct
9 Correct 10 ms 10332 KB Output is correct
10 Correct 16 ms 20564 KB Output is correct
11 Incorrect 9 ms 7380 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 27 ms 40660 KB Output is correct
3 Correct 8 ms 7252 KB Output is correct
4 Correct 23 ms 28624 KB Output is correct
5 Correct 46 ms 71352 KB Output is correct
6 Correct 23 ms 34264 KB Output is correct
7 Correct 9 ms 8148 KB Output is correct
8 Correct 8 ms 7508 KB Output is correct
9 Correct 10 ms 10332 KB Output is correct
10 Correct 16 ms 20564 KB Output is correct
11 Correct 10 ms 7356 KB Output is correct
12 Correct 26 ms 40656 KB Output is correct
13 Correct 9 ms 7380 KB Output is correct
14 Correct 23 ms 28616 KB Output is correct
15 Correct 47 ms 71372 KB Output is correct
16 Correct 27 ms 34260 KB Output is correct
17 Correct 8 ms 8148 KB Output is correct
18 Correct 8 ms 7500 KB Output is correct
19 Correct 9 ms 10452 KB Output is correct
20 Correct 17 ms 20692 KB Output is correct
21 Correct 10 ms 8276 KB Output is correct
22 Correct 9 ms 8300 KB Output is correct
23 Correct 358 ms 478176 KB Output is correct
24 Correct 10 ms 7380 KB Output is correct
25 Correct 301 ms 466616 KB Output is correct
26 Correct 291 ms 440272 KB Output is correct
27 Runtime error 218 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 27 ms 40660 KB Output is correct
3 Correct 8 ms 7252 KB Output is correct
4 Correct 23 ms 28624 KB Output is correct
5 Correct 46 ms 71352 KB Output is correct
6 Correct 23 ms 34264 KB Output is correct
7 Correct 9 ms 8148 KB Output is correct
8 Correct 8 ms 7508 KB Output is correct
9 Correct 10 ms 10332 KB Output is correct
10 Correct 16 ms 20564 KB Output is correct
11 Correct 10 ms 7356 KB Output is correct
12 Correct 26 ms 40656 KB Output is correct
13 Correct 9 ms 7380 KB Output is correct
14 Correct 23 ms 28616 KB Output is correct
15 Correct 47 ms 71372 KB Output is correct
16 Correct 27 ms 34260 KB Output is correct
17 Correct 8 ms 8148 KB Output is correct
18 Correct 8 ms 7500 KB Output is correct
19 Correct 9 ms 10452 KB Output is correct
20 Correct 17 ms 20692 KB Output is correct
21 Correct 10 ms 8276 KB Output is correct
22 Correct 9 ms 8300 KB Output is correct
23 Correct 358 ms 478176 KB Output is correct
24 Correct 10 ms 7380 KB Output is correct
25 Correct 301 ms 466616 KB Output is correct
26 Correct 291 ms 440272 KB Output is correct
27 Runtime error 218 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 27 ms 40660 KB Output is correct
3 Correct 8 ms 7252 KB Output is correct
4 Correct 23 ms 28624 KB Output is correct
5 Correct 46 ms 71352 KB Output is correct
6 Correct 23 ms 34264 KB Output is correct
7 Correct 9 ms 8148 KB Output is correct
8 Correct 8 ms 7508 KB Output is correct
9 Correct 10 ms 10332 KB Output is correct
10 Correct 16 ms 20564 KB Output is correct
11 Correct 10 ms 7356 KB Output is correct
12 Correct 26 ms 40656 KB Output is correct
13 Correct 9 ms 7380 KB Output is correct
14 Correct 23 ms 28616 KB Output is correct
15 Correct 47 ms 71372 KB Output is correct
16 Correct 27 ms 34260 KB Output is correct
17 Correct 8 ms 8148 KB Output is correct
18 Correct 8 ms 7500 KB Output is correct
19 Correct 9 ms 10452 KB Output is correct
20 Correct 17 ms 20692 KB Output is correct
21 Correct 10 ms 8276 KB Output is correct
22 Correct 9 ms 8300 KB Output is correct
23 Correct 358 ms 478176 KB Output is correct
24 Correct 10 ms 7380 KB Output is correct
25 Correct 301 ms 466616 KB Output is correct
26 Correct 291 ms 440272 KB Output is correct
27 Runtime error 218 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7268 KB Output isn't correct
2 Halted 0 ms 0 KB -