Submission #920957

#TimeUsernameProblemLanguageResultExecution timeMemory
920957shoryu386Kitchen (BOI19_kitchen)C++17
20 / 100
1 ms496 KiB
#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; sort(balls, balls+m); for (int bm = 0; bm < (1LL<<m); bm++){ if (__builtin_popcountll(bm) < k){ continue; } vector<int> chefs; for (int x = 0; x < m; x++){ if (bm & (1<<x)){ chefs.push_back(balls[x]); } } bool dead = false; for (int x = 0; x < n; x++){ if (buckets[x] > k){ dead = true; } } int chefsum = 0, bucketSum = 0; for (int x = 0; x < m; x++){ chefsum += chefs[x]; } for (int x = 0; x < n; x++){ bucketSum += buckets[x] - k + 1; chefsum -= (k-1); } if (dead){ continue; } if (chefsum >= bucketSum){ ans = min(ans, chefsum - bucketSum); } } if (ans == LLONG_MAX/20) {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)

kitchen.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...