Submission #1004262

#TimeUsernameProblemLanguageResultExecution timeMemory
1004262LilPlutonKitchen (BOI19_kitchen)C++14
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> /// author: LilPluton auuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu #define OPT ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define intt long long #define ll long long #define pb push_back #define arr array #define vll vector<int> #define fi first #define se second #define rep(i,j,k) for(int i = j; i <= k; ++i) #define all(a) a.begin(),a.end() #define pii pair<int,int> #define endll '\n' using namespace std; const ll INF = 1e18; const int N = 1e5 + 5; ll n, m, k, sum, chefsum; ll a[N], chef[N]; signed main() { cin >> n >> m >> k; for(ll i = 1; i <= n; ++i) cin >> a[i], sum += a[i]; sort(a + 1, a + n + 1); for(ll i = 1; i <= m; ++i) cin >> chef[i], chefsum += chef[i]; sort(chef + 1, chef + m + 1); if(k == 1) { ll i = 1, j = 1; ll ans = 0; while(i <= n && j <= m) { if(i > n || j > m) break; ll mn = min(a[i], chef[j]); a[i] -= mn; chef[j] -= mn; ans += chef[j]; if(a[i] == 0) ++i; if(chef[j] == 0) ++j; } if(i < n) { cout << "Impossible" << endll; } else cout << ans << endll; return 0; } if(m < k || a[1] < k) { cout << "Impossible" << endll; return 0; } ll ans = INF; for(ll mask = 1; mask < (1 << m); ++mask) { ll x = __builtin_popcount(mask); if(x < k) continue; ll s = 0, extra = 0; for (ll i = 0;i < m;i++) { if ((1 << i) & mask) { extra += chef[i + 1]; if (s < n * k) { s += min(n * k - s, min(chef[i + 1], n)); } } } if (extra >= sum && s == n * k) ans = min(ans, extra - sum); } if(ans == INF) cout << "Impossible"; else cout << ans << endll; }
#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...