oj.uz

Submission #678475

# Submission time Handle Problem Language Result Execution time Memory
678475 2023-01-06T04:40:55 Z cig32 Kitchen (BOI19_kitchen) C++17
100 / 100
 181 ms 219424 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;
}
int n, m, k, a[MAXN], b[MAXN];
void solve(int tc) {
  cin >> n >> m >> k;
  for(int i=1; i<=n; i++) {
    cin >> a[i];
    if(a[i] < k) {
      cout << "Impossible\n"; return;
    }
  }
  int sa = 0;
  for(int i=1; i<=n; i++) sa += a[i];
  for(int i=1; i<=m; i++) cin >> b[i];
  const int sum = 90000;
  int dp[m+1][sum+1];
  for(int i=0; i<=m; i++) for(int j=0; j<=sum; j++) dp[i][j] = -1e15;
  dp[0][0] = 0;
  int ans = 1e18;
  for(int i=1; i<=m; i++) {
    int bb = min(b[i], n);
    for(int j=0; j<=sum; j++) {
      dp[i][j] = dp[i-1][j];
      if(j >= b[i]) dp[i][j] = max(dp[i][j], dp[i-1][j - b[i]] + bb);
      if(j >= sa && dp[i][j] >= k * n) ans = min(ans, j - sa);
    }
  }
  if(ans == 1e18) cout << "Impossible\n";
  else cout << 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);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9424 KB Output is correct
2 Correct 10 ms 9424 KB Output is correct
3 Correct 10 ms 9428 KB Output is correct
4 Correct 10 ms 9448 KB Output is correct
5 Correct 10 ms 9428 KB Output is correct
6 Correct 9 ms 7376 KB Output is correct
7 Correct 8 ms 7380 KB Output is correct
8 Correct 10 ms 9428 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9424 KB Output is correct
2 Correct 10 ms 9424 KB Output is correct
3 Correct 10 ms 9428 KB Output is correct
4 Correct 10 ms 9448 KB Output is correct
5 Correct 10 ms 9428 KB Output is correct
6 Correct 9 ms 7376 KB Output is correct
7 Correct 8 ms 7380 KB Output is correct
8 Correct 10 ms 9428 KB Output is correct
9 Correct 19 ms 18644 KB Output is correct
10 Correct 19 ms 18644 KB Output is correct
11 Correct 19 ms 18644 KB Output is correct
12 Correct 21 ms 18612 KB Output is correct
13 Correct 17 ms 18552 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 191948 KB Output is correct
2 Correct 129 ms 167216 KB Output is correct
3 Correct 179 ms 219424 KB Output is correct
4 Correct 179 ms 219420 KB Output is correct
5 Correct 148 ms 212376 KB Output is correct
6 Correct 116 ms 154536 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 36180 KB Output is correct
2 Correct 36 ms 36248 KB Output is correct
3 Correct 31 ms 36152 KB Output is correct
4 Correct 38 ms 36248 KB Output is correct
5 Correct 9 ms 7316 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9424 KB Output is correct
2 Correct 10 ms 9424 KB Output is correct
3 Correct 10 ms 9428 KB Output is correct
4 Correct 10 ms 9448 KB Output is correct
5 Correct 10 ms 9428 KB Output is correct
6 Correct 9 ms 7376 KB Output is correct
7 Correct 8 ms 7380 KB Output is correct
8 Correct 10 ms 9428 KB Output is correct
9 Correct 19 ms 18644 KB Output is correct
10 Correct 19 ms 18644 KB Output is correct
11 Correct 19 ms 18644 KB Output is correct
12 Correct 21 ms 18612 KB Output is correct
13 Correct 17 ms 18552 KB Output is correct
14 Correct 160 ms 191948 KB Output is correct
15 Correct 129 ms 167216 KB Output is correct
16 Correct 179 ms 219424 KB Output is correct
17 Correct 179 ms 219420 KB Output is correct
18 Correct 148 ms 212376 KB Output is correct
19 Correct 116 ms 154536 KB Output is correct
20 Correct 31 ms 36180 KB Output is correct
21 Correct 36 ms 36248 KB Output is correct
22 Correct 31 ms 36152 KB Output is correct
23 Correct 38 ms 36248 KB Output is correct
24 Correct 9 ms 7316 KB Output is correct
25 Correct 117 ms 155944 KB Output is correct
26 Correct 146 ms 179260 KB Output is correct
27 Correct 118 ms 120788 KB Output is correct
28 Correct 159 ms 179964 KB Output is correct
29 Correct 146 ms 184084 KB Output is correct
30 Correct 181 ms 219416 KB Output is correct