Submission #1095576

#TimeUsernameProblemLanguageResultExecution timeMemory
1095576MateiKing80Kitchen (BOI19_kitchen)C++14
100 / 100
17 ms1176 KiB
#include <bits/stdc++.h> using namespace std; const int N = 300 * 301; int n, m, k, dp[N + 5], a[300], b[300], sum = 0; int ldr[N + 5]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> k; int minn = 1e9; for(int i = 0; i < n; i ++) { cin >> a[i]; ldr[a[i]] ++; sum += a[i]; minn = min(minn, a[i]); } if(minn < k) { for(int i = 0; i < m; i ++) cin >> n; cout << "Impossible"; return 0; } for(int i = N; i >= 0; i --) ldr[i] += ldr[i + 1]; for(int i = 1; i <= N; i ++) dp[i] = -1e9; for(int i = 0; i < m; i ++) { cin >> b[i]; for(int j = N; j >= b[i]; j --) dp[j] = max(dp[j], min(b[i], n) + dp[j - b[i]]); } for(int i = sum; i <= 300 * 301; i ++) if (dp[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...