Submission #444803

#TimeUsernameProblemLanguageResultExecution timeMemory
444803zxcvbnmKitchen (BOI19_kitchen)C++14
100 / 100
81 ms1056 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int INF = 1e9 + 5; const int maxN = 305; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; vector<int> a(n), b(m); for(int& i : a) { cin >> i; } for(int& i : b) { cin >> i; } int ans = INF; for(int i : a) { if (i < k) { cout << "Impossible\n"; exit(0); } } int time = accumulate(a.begin(), a.end(), 0); vector<int> last(maxN*maxN, -INF); last[0] = 0; vector<int> curr(maxN*maxN, -INF); for(int i = 1; i <= m; i++) { for(int j = 0; j < maxN*maxN; j++) { curr[j] = last[j]; if (j-b[i-1] < 0) continue; curr[j] = max(curr[j], last[j-b[i-1]] + min(n, b[i-1])); if (curr[j] >= k*n && j >= time && j-time < ans) { ans = j-time; } } last = curr; } if (ans == INF) { cout << "Impossible\n"; } else { cout << ans << "\n"; } return 0; }
#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...