# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
921107 | shoryu386 | Kitchen (BOI19_kitchen) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
]#include <bits/stdc++.h>
using namespace std;
#define int long long
main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m, k; cin >> n >> m >> k;
int buckets[n], balls[m];
for (int x = 0; x < n; x++) cin >> buckets[x];
for (int x = 0; x < m; x++) cin >> balls[x];
#define IMP cout << "Impossible"; return 0;
bool dead = false;
for (int x = 0; x < n; x++){
if (buckets[x] < k){
dead = true;
}
}
if (dead) {IMP;}
int bucketsum = 0;
for (int x = 0; x < n; x++){
bucketsum += buckets[x];
}
#define BSMAX 100000
bitset<BSMAX> hmm[n*k+1];
hmm[n*k][0] = 1;
for (int x = 0; x < m; x++){
for (int z = n*(k-x-1); z <= n*(k-x); z++){
hmm[max(0LL, z - min(balls[x], n))] |= (hmm[z] << balls[x]);
}
}
int ans = -1;
for (int x = bucketsum; x < BSMAX; x++){
if (hmm[0][x]){
ans = x-bucketsum;
break;
}
}
if (ans == -1) cout << "Impossible";
else cout << ans;
}