# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
920938 | shoryu386 | Kitchen (BOI19_kitchen) | C++17 | 1 ms | 600 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;
/*
if (m == 1){
//st1 pt 1
if (k > 1){
IMP;
}
int bucketsum = 0;
for (int x = 0; x < n; x++){
bucketsum += buckets[x];
}
if (bucketsum > balls[0]){
IMP;
}
cout << balls[0] - bucketsum;
}
else if (m == 2){
//st1 pt2
if (k > 2){
IMP;
}
else if (k == 2){
}
else{
}
}
*/
if (m <= 15){
int ans = LLONG_MAX/20;
for (int bm = 0; bm < (1LL<<m); bm++){
vector<int> chefs;
for (int x = 0; x < m; x++){
if (bm & (1<<x)){
chefs.push_back(balls[x]);
}
}
sort(chefs.begin(), chefs.end());
if (chefs.size() < k){
continue;
}
priority_queue<int> chefsLeft;
for (auto y : chefs) chefsLeft.push(y);
for (int x = 0; x < (k-1)*n; x++){
int cur = chefsLeft.top();
cur--;
chefsLeft.pop();
chefsLeft.push(cur);
}
chefs.clear();
bool dead = false;
while (!chefsLeft.empty()){
if (chefsLeft.top() < 0){
dead = true;
break;
}
chefs.push_back(chefsLeft.top());
chefsLeft.pop();
}
if (dead){
continue;
}
reverse(chefs.begin(), chefs.end()); //sorted again
#define BSMAX 100000
//300^2
bitset<BSMAX> bs;
bs[0] = 1;
for (int x = 0; x < (int)(chefs.size()); x++){
bs |= (bs << chefs[x]);
}
int bucketsum = 0;
for (int x = 0; x < n; x++){
bucketsum += (buckets[x] - (k-1));
}
int curans = -1;
for (int x = bucketsum; x < BSMAX; x++){
if (bs[x]){
curans = x-bucketsum;
break;
}
}
if (curans != -1) ans = min(curans, ans);
}
if (ans == -1) {IMP;}
else cout << ans;
}
else if (k == 1){
//subtask 3
#define BSMAX 100000
//300^2
bitset<BSMAX> bs;
bs[0] = 1;
for (int x = 0; x < m; x++){
bs |= (bs << balls[x]);
}
int bucketsum = 0;
for (int x = 0; x < n; x++){
bucketsum += buckets[x];
}
int ans = -1;
for (int x = bucketsum; x < BSMAX; x++){
if (bs[x]){
ans = x-bucketsum;
break;
}
}
if (ans == -1) cout << "Impossible";
else cout << ans;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |