#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18, BOUND = 10000;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll M, L;
cin >> M >> L;
ll A[2*M+1];
for (ll i = 0; i <= 2*M; i++) cin >> A[i];
ll sum = 0, cnt = 0;
for (ll i = 0; i <= 2*M; i++) sum += (i-M)*A[i], cnt += A[i];
if (sum < L) {
cout << "impossible";
return 0;
} else if (L == 0) {
cout << A[0];
return 0;
}
ll idx = -1, take = -1;
for (ll i = 2*M; i >= M+1; i--) {
if (sum-(i-M)*A[i] > L) {
sum -= (i-M)*A[i];
cnt -= A[i];
} else {
idx = i-M;
take = (sum-L)/(i-M);
sum -= (i-M)*take;
cnt -= take;
}
}
ll knap_min[BOUND];
fill(knap_min, knap_min+BOUND, INF);
knap_min[0] = 0;
for (ll i = 1; i < idx; i++) {
for (ll j = BOUND-1; j >= 0; j--) {
for (ll k = 1; j-i*k >= 0 && k <= A[M+i]; k++) {
knap_min[j] = min(knap_min[j], knap_min[j-i*k]+k);
}
}
}
for (ll j = BOUND-1; j >= 0; j--) {
for (ll k = 1; j-idx*k >= 0 && k <= A[M+idx]-take; k++) {
knap_min[j] = min(knap_min[j], knap_min[j-idx*k]+k);
}
}
ll knap_max[BOUND];
fill(knap_max, knap_max+BOUND, -INF);
knap_max[0] = 0;
for (ll i = idx+1; i <= M; i++) {
for (ll j = BOUND-1; j >= 0; j--) {
for (ll k = 1; j-i*k >= 0 && k <= A[M+i]; k++) {
knap_max[j] = max(knap_max[j], knap_max[j-i*k]+k);
}
}
}
for (ll j = BOUND-1; j >= 0; j--) {
for (ll k = 1; j-idx*k >= 0 && k <= take; k++) {
knap_max[j] = max(knap_max[j], knap_max[j-idx*k]+k);
}
}
ll goal = sum-L, ans = -INF;
for (ll i = goal; i < BOUND; i++) {
ans = max(ans, cnt-knap_min[i]+knap_max[i-goal]);
}
if (ans == -INF) cout << "impossible";
else cout << ans;
return 0;
}
/*
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... |