Submission #1189951

#TimeUsernameProblemLanguageResultExecution timeMemory
1189951crafticatOlympiads (BOI19_olympiads)C++20
0 / 100
201 ms77572 KiB
#include <bits/stdc++.h> using namespace std; #define F0R(i, n) for (int i = 0; i < n;i++) #define FOR(i, j, n) for(int i = j; i < n;i++) template<typename T> using V = vector<T>; using vi = V<int>; constexpr int INF = 1e9; int main() { int n, m, k; cin >> n >> m >> k; vi a(n), b(m); int sumB = 0, sumA = 0; F0R(i, n) cin >> a[i]; F0R(i, m) cin >> b[i]; swap(a, b); swap(m, n); for (auto x : b) sumB += x; for (auto x : a) sumA += x; F0R(i, m) { if (b[i] < k) { cout << "Impossible\n"; return 0; } } int BOUND = max(sumB, sumA) + 1; vi dp(BOUND, -INF); dp[0] = 0; F0R(i, n) { vi newDp = dp; F0R(j, BOUND) { if (j - a[i] >= 0) newDp[j] = dp[j - a[i]]; } dp = newDp; } FOR(i, sumB, BOUND) { if (dp[i] >= 0) { cout << i - sumB << endl; return 0; } } cout << "Impossible\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...