#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18, BOUND = 1e6+10;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll M, L;
cin >> M >> L;
if (L+BOUND/2 < 0 || L+BOUND/2 >= BOUND) {
cout << "impossible";
return 0;
}
ll A[2*M+1];
for (ll i = 0; i <= 2*M; i++) cin >> A[i];
ll knap[BOUND];
fill(knap, knap+BOUND, -INF);
knap[BOUND/2] = A[M];
// subtract
for (ll i = 1; i <= M; i++) {
for (ll j = 0; j < BOUND; j++) {
for (ll k = 1; k <= A[M-i] && j + i*k < BOUND; k++) {
knap[j] = max(knap[j], knap[j+i*k]+k);
}
}
}
// add
for (ll i = 1; i <= M; i++) {
for (ll j = BOUND-1; j >= 0; j--) {
for (ll k = 1; k <= A[M+i] && j - i*k >= 0; k++) {
knap[j] = max(knap[j], knap[j-i*k]+k);
}
}
}
ll val = knap[L+BOUND/2];
if (val < 0) cout << "impossible";
else cout << val;
return 0;
}
/*
2 5
2 3 1 1 4
*/
/*
3 5
3 1 0 2 0 0 2
*/
/*
1 5
0 0 6
*/
# | 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... |
# | 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... |