#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 3e2+1;
const int MOD = 1e9+7;
int n,m,k,a[N],b[N],dp[N][90001];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> k;
if(m < k){
cout << "Impossible";
return 0;
}
int tot = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
if(a[i] < k){
cout << "Impossible";
return 0;
}
tot += a[i];
}
int sum = 0;
for(int i = 1; i <= m; i++){
cin >> b[i];
sum += b[i];
}
if(sum < tot){
cout << "Impossible";
return 0;
}
for(int i = 0; i <= m; i++){
for(int j = 0; j <= sum; j++) dp[i][j] = -1e9;
}
dp[0][0] = 0;
for(int i = 1; i <= m; i++){
for(int j = 0; j <= sum; j++){
dp[i][j] = dp[i-1][j];
if(j >= b[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-b[i]]+min(n,b[i]));
}
}
//cout << dp[1][4];
for(int j = tot; j <= sum; j++){
//cout << dp[m][j];
if(dp[m][j] < n*k) continue;
cout << j-tot;
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... |