Submission #1076865

#TimeUsernameProblemLanguageResultExecution timeMemory
1076865Mizo_CompilerKitchen (BOI19_kitchen)C++17
0 / 100
26 ms1172 KiB
#include <bits/stdc++.h> using namespace std; int n, m, k, dp[(300 * 303)], a[300], b[300], sum = 0; int gt[(300*303)]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> k; int mn = 1e9; for (int i = 0; i < n; i++) { cin >> a[i]; gt[a[i]]++; sum += a[i]; mn = min(mn, a[i]); } if (mn < k) { cout << "Impossible"; return 0; } for (int i = 300*301; i >= 0; i--) { gt[i] += gt[i+1]; } for (int i = 0; i < m; i++) { cin >> b[i]; for (int j = 300*301; j >= b[i]; j--) { dp[j] = max(dp[j], min(b[i], gt[dp[j-b[i]]+1]) + 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...