Submission #863005

#TimeUsernameProblemLanguageResultExecution timeMemory
863005ArashJafariyanKitchen (BOI19_kitchen)C++17
52 / 100
312 ms262144 KiB
#include <bits/stdc++.h> using namespace std; const int N = 300 + 4; int n, m, k, a[N], b[N]; bitset<N * N> dp[N * N], save[N * N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; bool ok = 1; int s = 0; for (int i = 0; i < n; i++) { cin >> a[i]; if (a[i] < k) ok = 0; s += a[i]; } for (int i = 0; i < m; i++) cin >> b[i]; if (!ok) { cout << "Impossible"; return 0; } dp[0][0] = 1; for (int i = 0; i < m; i++) { for (int j = 0; j <= m * n; j++) save[j] = dp[j]; for (int j = 0; j <= m * n; j++) dp[j + min(b[i], n)] |= (save[j] << b[i]); } int ans = INT_MAX; for (int i = n * k; i <= n * m; i++) for (int j = s; j <= m * N; j++) if (dp[i][j]) ans = min(ans, j); if (ans == INT_MAX) cout << "Impossible"; else cout << ans - s; 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...