#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |