This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 333;
int n, m, k;
int A[N];
int B[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
cin >> A[i];
for (int i = 0; i < m; i++)
cin >> B[i];
if (*min_element(A, A + n) < k) {
cout << "Impossible\n";
return 0;
}
sort(B, B + m);
int sum = 0;
for (int i = 0; i < m; i++) sum += B[i];
vector<vector<int>> dp(sum + 1, vector<int>(k + 1, 0));
vector<bool> us(sum + 1);
us[0] = true;
dp[0][0] = 1e9;
for (int i = 0; i < m; i++) {
for (int s = sum; s >= B[i]; s--) {
us[s] = (us[s] | us[s - B[i]]);
if (!us[s - B[i]]) continue;
dp[s][1] = s;
for (int j = 2; j <= k; j++) {
dp[s][j] = max(dp[s][j], min(s / j, dp[s - B[i]][j - 1]));
}
}
}
int x = 0;
for (int i = 0; i < n; i++) x += A[i];
for (int i = x; i <= sum; i++) {
if (dp[i][k] >= n) {
cout << i - x << '\n';
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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |