Submission #315775

#TimeUsernameProblemLanguageResultExecution timeMemory
315775FlashGamezzzKitchen (BOI19_kitchen)C++17
100 / 100
88 ms1144 KiB
#include <iostream> #include <cstdlib> #include <cstdio> #include <fstream> #include <algorithm> #include <string> using namespace std; int n, m, k, sum = 0, last[90001], dp[90001] = {}; int main() { ios_base::sync_with_stdio(false); cin >> n >> m >> k; for (int i = 0; i < n; i++){ int a; cin >> a; if (a < k){ cout << "Impossible" << endl; return 0; } sum += a; } last[0] = 0; for (int i = 1; i <= 90000; i++){ last[i] = -1; dp[i] = -1; } for (int i = 0; i < m; i++){ int c; cin >> c; for (int j = 0; j <= 90000-c; j++){ if (last[j] >= 0){ dp[j] = max(dp[j], last[j]); dp[j+c] = max(dp[j+c], last[j]+min(n, c)); } } swap(dp, last); for (int j = 0; j <= 90000; j++){ dp[j] = -1; } } for (int i = sum; i <= 90000; i++){ if (last[i] >= n*k){ cout << i-sum; return 0; } } cout << "Impossible" << endl; }
#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...