Submission #1226761

#TimeUsernameProblemLanguageResultExecution timeMemory
1226761namhhKitchen (BOI19_kitchen)C++20
100 / 100
70 ms100424 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fi first #define se second const int N = 3e2+1; const int MOD = 1e9+7; int n,m,k,a[N],b[N],dp[N][90001]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> k; if(m < k){ cout << "Impossible"; return 0; } int tot = 0; for(int i = 1; i <= n; i++){ cin >> a[i]; if(a[i] < k){ cout << "Impossible"; return 0; } tot += a[i]; } int sum = 0; for(int i = 1; i <= m; i++){ cin >> b[i]; sum += b[i]; } if(sum < tot){ cout << "Impossible"; return 0; } for(int i = 0; i <= m; i++){ for(int j = 0; j <= sum; j++) dp[i][j] = -1e9; } dp[0][0] = 0; for(int i = 1; i <= m; i++){ for(int j = 0; j <= sum; j++){ dp[i][j] = dp[i-1][j]; if(j >= b[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-b[i]]+min(n,b[i])); } } //cout << dp[1][4]; for(int j = tot; j <= sum; j++){ //cout << dp[m][j]; if(dp[m][j] < n*k) continue; cout << j-tot; 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...