Submission #758817

#TimeUsernameProblemLanguageResultExecution timeMemory
758817HanksburgerKitchen (BOI19_kitchen)C++17
100 / 100
72 ms106316 KiB
#include <bits/stdc++.h> using namespace std; int dp[305][90005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, k, sum=0; cin >> n >> m >> k; for (int i=1; i<=n; i++) { int x; cin >> x; if (x<k) { cout << "Impossible"; return 0; } sum+=x; } for (int i=1; i<=90000; i++) dp[0][i]=-1e9; for (int i=1; i<=m; i++) { int x; cin >> x; for (int j=0; j<=90000; j++) dp[i][j]=max(dp[i-1][j], j>=x?(dp[i-1][j-x]+min(x, n)):(int)(-1e9)); } for (int i=sum; i<=90000; i++) { if (dp[m][i]>=n*k) { cout << i-sum; return 0; } } cout << "Impossible"; }
#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...