#include <bits/stdc++.h>
using namespace std;
const int MX = 305;
const int INF = 1e9 + 7;
int N, M, K, a[MX], b[MX], dp[2][MX * MX], tot = 0;
void chmax(int& a, int b){
if(b > a) a = b;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M >> K;
for(int i = 0; i < N; i++) cin >> a[i];
for(int j = 0; j < M; j++) cin >> b[j];
bool f = true;
for(int i = 0; i < N; i++){
if(a[i] < K) f = false;
tot += a[i];
}
if(!f){
cout << "Impossible\n";
return 0;
}
for(int j = 0; j <= 300 * M; j++) dp[0][j] = -INF;
dp[0][0] = 0;
int id = 1;
for(int i = 0; i < M; i++){
for(int j = 0; j <= 300 * M; j++){
chmax(dp[id][j + b[i]], dp[id ^ 1][j] + min(b[i], N));
chmax(dp[id][j], dp[id ^ 1][j]);
}
id ^= 1;
}
for(int j = tot; j <= 300 * M; j++){
if(dp[M][j] >= N * K){
cout << j - tot << '\n';
return 0;
}
}
cout << "Impossible\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
23 ms |
1720 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |