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;
typedef long long ll;
int main(){
ll n, m, k; cin >> n >> m >> k;
vector <ll> a(n), b(n);
ll flag = m, sum = 0;
for (int i = 0; i < n; i++){
cin >> a[i];
flag = min(flag, a[i]);
sum += a[i];
}
if (flag < k){
cout << "impossible";
return 0;
}
for (int i = 0; i < m; i++)cin >> b[i];
vector<ll> dp(9001, -10000);
dp[0] = 0;
for (int i = 0; i < m; i++){
for (int j = 9000-b[i]; j >= 0; j--)dp[j+b[i]] = max(dp[j+b[i]], dp[j]+min(n, b[i]));
}
for (int i = sum; i <= 9000; i++){
if (dp[i] >= n*k){
cout << i-sum;
return 0;
}
}
cout << "impossible";
}
# | 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... |