oj.uz

Submission #605589

# Submission time Handle Problem Language Result Execution time Memory
605589 2022-07-25T19:08:03 Z slime Kitchen (BOI19_kitchen) C++14
100 / 100
 162 ms 219364 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);
}
// I don't know geometry.
// Teaming is unfair.

/*

*/

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9428 KB Output is correct
2 Correct 10 ms 9428 KB Output is correct
3 Correct 9 ms 9428 KB Output is correct
4 Correct 9 ms 9428 KB Output is correct
5 Correct 10 ms 9428 KB Output is correct
6 Correct 9 ms 7380 KB Output is correct
7 Correct 8 ms 7376 KB Output is correct
8 Correct 8 ms 9428 KB Output is correct
9 Correct 18 ms 18644 KB Output is correct
10 Correct 16 ms 18648 KB Output is correct
11 Correct 16 ms 18568 KB Output is correct
12 Correct 15 ms 18644 KB Output is correct
13 Correct 17 ms 18644 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 191940 KB Output is correct
2 Correct 118 ms 167284 KB Output is correct
3 Correct 152 ms 219340 KB Output is correct
4 Correct 150 ms 219340 KB Output is correct
5 Correct 143 ms 212364 KB Output is correct
6 Correct 118 ms 154508 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 36152 KB Output is correct
2 Correct 29 ms 36180 KB Output is correct
3 Correct 28 ms 36180 KB Output is correct
4 Correct 34 ms 36172 KB Output is correct
5 Correct 8 ms 7324 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9428 KB Output is correct
2 Correct 10 ms 9428 KB Output is correct
3 Correct 9 ms 9428 KB Output is correct
4 Correct 9 ms 9428 KB Output is correct
5 Correct 10 ms 9428 KB Output is correct
6 Correct 9 ms 7380 KB Output is correct
7 Correct 8 ms 7376 KB Output is correct
8 Correct 8 ms 9428 KB Output is correct
9 Correct 18 ms 18644 KB Output is correct
10 Correct 16 ms 18648 KB Output is correct
11 Correct 16 ms 18568 KB Output is correct
12 Correct 15 ms 18644 KB Output is correct
13 Correct 17 ms 18644 KB Output is correct
14 Correct 162 ms 191940 KB Output is correct
15 Correct 118 ms 167284 KB Output is correct
16 Correct 152 ms 219340 KB Output is correct
17 Correct 150 ms 219340 KB Output is correct
18 Correct 143 ms 212364 KB Output is correct
19 Correct 118 ms 154508 KB Output is correct
20 Correct 29 ms 36152 KB Output is correct
21 Correct 29 ms 36180 KB Output is correct
22 Correct 28 ms 36180 KB Output is correct
23 Correct 34 ms 36172 KB Output is correct
24 Correct 8 ms 7324 KB Output is correct
25 Correct 111 ms 155888 KB Output is correct
26 Correct 122 ms 179248 KB Output is correct
27 Correct 85 ms 120784 KB Output is correct
28 Correct 136 ms 180024 KB Output is correct
29 Correct 131 ms 184140 KB Output is correct
30 Correct 161 ms 219364 KB Output is correct