Submission #567217

#TimeUsernameProblemLanguageResultExecution timeMemory
567217RifalKitchen (BOI19_kitchen)C++14
9 / 100
1097 ms215244 KiB
#include <bits/stdc++.h> #include <fstream> #define endl '\n' #define mod 32768 #define INF 100000000 //#define ll long long //#define cin fin //#define cout fout using namespace std; //ofstream fout("convention.out"); //ifstream fin("convention.in"); const int M = 9e4 + 5; const int N = 300 + 5; pair<bool,int> dp[M][N] = {}; void add(int x) { for(int i = M-1; i >= x; i--) { for(int j = 1; j < N; j++) { if(dp[i-x][j-1].first) { dp[i][j].first = 1; dp[i][j].second = min(dp[i][j].second,x); } } } } int main() { int n, m, k; cin >> n >> m >> k; int meal[n], chef[m]; dp[0][0].first = 1; for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { dp[i][j].second = INF; } } long long sum = 0; bool ok = true; for(int i = 0; i < n; i++) { cin >> meal[i]; if(meal[i] < k) ok = false; sum += meal[i]; } for(int i = 0; i < m; i++) { cin >> chef[i]; add(chef[i]); } if(m < k || ok == false) { cout << "Impossible"; return 0; } for(int i = sum; i < M; i++) { for(int j = k; j < N; j++) { if(dp[i][j].first == 1 && dp[i][j].second >= k && dp[i][j].second != INF) { cout << i-sum; return 0; } } } cout << "Impossible"; 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...