#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 303030
#define MAXS 19
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define smin(a, x) (a)=(min((a), (x)))
ll arr[MAX];
ll dp[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int M;
ll L;
cin >> M >> L;
int i;
ll A, B;
A = B = 0;
for (i = -M; i <= M; i++) cin >> arr[i + M], (i < 0 ? A : B) += arr[i + M] * i;
if (B < L || A > L) {
cout << "impossible" << ln;
return 0;
}
if (A + B <= L) reverse(arr, arr + M + M + 1), L *= -1, swap(A, B), A *= -1, B *= -1;
ll cnt = 0;
if (A + B == L) {
for (i = -M; i <= M; i++) cnt += arr[i + M];
cout << cnt << ln;
return 0;
}
for (i = -M; i < 0; i++) cnt += arr[i + M];
int c = 0;
for (i = 1; i <= M; i++) {
if (A + arr[i + M] * i > L) {
ll x = (L - A) / i;
if (x) c = x;
A += x * i;
cnt += x;
break;
}
else A += arr[i + M] * i, cnt += arr[i + M];
}
int e = i;
A = L - A;
vector<tuple<ll, ll, ll>> lst;
for (i = -M; i < 0; i++) if (arr[i + M]) lst.emplace_back(-i, 1, arr[i + M]);
for (i = e; i <= M; i++) if (arr[i + M]) lst.emplace_back(i, -1, arr[i + M]);
for (i = 1; i < e; i++) if (arr[i + M]) lst.emplace_back(-i, 1, arr[i + M]);
if (c) lst.emplace_back(e, 1, c);
fill(dp, dp + 303000, M * 100);
int bias = M * M + 20;
dp[bias] = 0;
for (auto& [w, v, mx] : lst) {
int ww = abs(w);
vector<priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>> vpq(ww);
if (w < 0) {
for (i = M * M + 10; i >= -M * M - 10; i--) {
int ind = (i % ww + ww) % ww;
while (vpq[ind].size() && vpq[ind].top().second > i + M * mx) vpq[ind].pop();
int pv = dp[i + bias];
if (vpq[ind].size()) dp[i + bias] = min(dp[i + bias], vpq[ind].top().first - v * (i / ww));
vpq[ind].emplace(pv + v * (i / ww), i);
}
}
else {
for (i = -M * M - 10; i <= M * M + 10; i++) {
int ind = (i % ww + ww) % ww;
while (vpq[ind].size() && vpq[ind].top().second < i - M * mx) vpq[ind].pop();
int pv = dp[i + bias];
if (vpq[ind].size()) dp[i + bias] = min(dp[i + bias], vpq[ind].top().first + v * (i / ww));
vpq[ind].emplace(pv - v * (i / ww), i);
}
}
}
if (dp[bias + A] > 50 * M) cout << "impossible" << ln;
else cout << cnt + arr[M] - dp[bias + A];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
21 ms |
2944 KB |
Output is correct |
7 |
Correct |
9 ms |
2900 KB |
Output is correct |
8 |
Correct |
21 ms |
2924 KB |
Output is correct |
9 |
Correct |
22 ms |
2960 KB |
Output is correct |
10 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
21 ms |
2944 KB |
Output is correct |
7 |
Correct |
9 ms |
2900 KB |
Output is correct |
8 |
Correct |
21 ms |
2924 KB |
Output is correct |
9 |
Correct |
22 ms |
2960 KB |
Output is correct |
10 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2716 KB |
Output is correct |
2 |
Correct |
4 ms |
2772 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2716 KB |
Output is correct |
2 |
Correct |
4 ms |
2772 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2716 KB |
Output is correct |
2 |
Correct |
4 ms |
2772 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
21 ms |
2944 KB |
Output is correct |
7 |
Correct |
9 ms |
2900 KB |
Output is correct |
8 |
Correct |
21 ms |
2924 KB |
Output is correct |
9 |
Correct |
22 ms |
2960 KB |
Output is correct |
10 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2716 KB |
Output is correct |
2 |
Correct |
4 ms |
2772 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
21 ms |
2944 KB |
Output is correct |
7 |
Correct |
9 ms |
2900 KB |
Output is correct |
8 |
Correct |
21 ms |
2924 KB |
Output is correct |
9 |
Correct |
22 ms |
2960 KB |
Output is correct |
10 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2716 KB |
Output is correct |
2 |
Correct |
4 ms |
2772 KB |
Output is correct |
3 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
21 ms |
2944 KB |
Output is correct |
7 |
Correct |
9 ms |
2900 KB |
Output is correct |
8 |
Correct |
21 ms |
2924 KB |
Output is correct |
9 |
Correct |
22 ms |
2960 KB |
Output is correct |
10 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |