oj.uz

Submission #605575

# Submission time Handle Problem Language Result Execution time Memory
605575 2022-07-25T18:57:22 Z slime Kitchen (BOI19_kitchen) C++14
31 / 100
 18 ms 7380 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];

bool cookable(vector<int> vt) { // vt: chefs' working hours
  if(vt.size() < k) return 0;
  int sm = 0;
  for(int x: vt) sm += min(b[x], n);
  if(sm < k * n) return 0;
  return 1;
}
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=0; i<m; i++) cin >> b[i];
  int ans = 1e18;
  for(int i=0; i<(1<<m); i++) {
    vector<int> vt;
    for(int j=0; j<m; j++) if(i & (1<<j)) vt.push_back(j);
    int sm = 0;
    for(int x: vt) sm += b[x];
    if(cookable(vt) && sm >= sa) {
      ans = min(ans, sm - sa);
    }
  }
  cout << (ans == 1e18 ? "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

kitchen.cpp: In function 'bool cookable(std::vector<long long int>)':
kitchen.cpp:67:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   67 |   if(vt.size() < k) return 0;
      |      ~~~~~~~~~~^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7380 KB Output is correct
2 Correct 8 ms 7276 KB Output is correct
3 Correct 7 ms 7324 KB Output is correct
4 Correct 8 ms 7376 KB Output is correct
5 Correct 8 ms 7380 KB Output is correct
6 Correct 7 ms 7372 KB Output is correct
7 Correct 8 ms 7380 KB Output is correct
8 Correct 8 ms 7380 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7380 KB Output is correct
2 Correct 8 ms 7276 KB Output is correct
3 Correct 7 ms 7324 KB Output is correct
4 Correct 8 ms 7376 KB Output is correct
5 Correct 8 ms 7380 KB Output is correct
6 Correct 7 ms 7372 KB Output is correct
7 Correct 8 ms 7380 KB Output is correct
8 Correct 8 ms 7380 KB Output is correct
9 Correct 14 ms 7252 KB Output is correct
10 Correct 15 ms 7380 KB Output is correct
11 Correct 14 ms 7360 KB Output is correct
12 Correct 15 ms 7332 KB Output is correct
13 Correct 18 ms 7380 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7380 KB Output is correct
2 Correct 8 ms 7276 KB Output is correct
3 Correct 7 ms 7324 KB Output is correct
4 Correct 8 ms 7376 KB Output is correct
5 Correct 8 ms 7380 KB Output is correct
6 Correct 7 ms 7372 KB Output is correct
7 Correct 8 ms 7380 KB Output is correct
8 Correct 8 ms 7380 KB Output is correct
9 Correct 14 ms 7252 KB Output is correct
10 Correct 15 ms 7380 KB Output is correct
11 Correct 14 ms 7360 KB Output is correct
12 Correct 15 ms 7332 KB Output is correct
13 Correct 18 ms 7380 KB Output is correct
14 Incorrect 7 ms 7348 KB Output isn't correct
15 Halted 0 ms 0 KB -