#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;
using ll = long long;
template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }
using namespace std;
constexpr ll inf = 1e18;
ll gcd(ll a, ll b) {
a = abs(a); b = abs(b);
while (b) {
a %= b;
swap(a, b);
}
return a;
}
int main() {
int M; cin >> M;
ll L; cin >> L;
vector<ll> A(2 * M + 1);
rep (i, 2 * M + 1) cin >> A[i];
if (L < 0) {
reverse(all(A));
L = -L;
}
ll sml = 0, smr = 0;
rep (i, 2 * M + 1) {
if (i < M) sml += A[i] * (i - M);
if (i > M) smr += A[i] * (i - M);
}
if (L < sml || smr < L) {
puts("impossible");
return 0;
}
vector<pair<int, ll>> B;
vector<pair<int, ll>> C;
rep (i, 2 * M + 1) {
if (i == M) continue;
if (A[i] == 0) continue;
if (A[i] <= M && i <= M / 2) B.emplace_back(i - M, A[i]);
else C.emplace_back(i - M, A[i]);
}
sml = smr = 0;
for (auto [x, y] : B) {
if (x < 0) sml += x * y;
else smr += x * y;
}
auto calc_dp = [](vector<pair<int, ll>> B) -> vector<ll> {
ll sml = 0, smr = 0;
for (auto [x, y] : B) {
if (x < 0) sml += x * y;
else smr += x * y;
}
vector<ll> dp(smr - sml + 1, -inf);
dp[0 - sml] = 0;
for (auto [x, y] : B) {
int ax = abs(x);
vector<ll> memo;
vector<ll> res;
deque<int> st;
rep (i, ax) {
// mod x ごとにスライド最大値の形になる
memo.clear();
for (int j = i; j <= smr - sml; j += ax) {
memo.push_back(dp[j]);
}
res.assign(memo.size(), -inf);
st.clear();
if (x > 0) {
rep (i, memo.size()) memo[i] -= i;
rep (i, res.size()) {
while (!st.empty() && st.front() < i - y) st.pop_front();
while (!st.empty() && memo[st.back()] < memo[i]) st.pop_back();
st.push_back(i);
res[i] = memo[st.front()] + i;
}
}
else {
rep (i, memo.size()) memo[i] += i;
rrep (i, res.size()) {
while (!st.empty() && st.front() > i + y) st.pop_front();
while (!st.empty() && memo[st.back()] < memo[i]) st.pop_back();
st.push_back(i);
res[i] = memo[st.front()] - i;
}
}
rep (j, res.size()) dp[j * ax + i] = res[j];
}
}
return dp;
};
auto dp = calc_dp(B);
if (C.empty()) {
if (dp[L - sml] >= 0) {
cout << dp[L - sml] + A[M] << endl;
}
else {
puts("impossible");
}
return 0;
}
if (C.size() <= 1) {
auto [x, y] = C[0];
ll lo = 0, hi = x * y;
if (lo > hi) swap(lo, hi);
ll ans = -inf;
rep (i, smr - sml + 1) {
if (dp[i] < 0) continue;
if (L < (i + sml) + lo || (i + sml) + hi < L) continue;
if ((L - (i + sml)) % x) continue;
chmax(ans, dp[i] + A[M] + abs((L - (i + sml)) / x));
}
if (ans >= 0) {
cout << ans << endl;
}
else {
puts("impossible");
}
return 0;
}
auto calc_dp2 = [](vector<pair<int, ll>> B, ll mx) -> vector<vector<ll>> {
ll sml = 0, smr = 0;
for (auto [x, y] : B) {
if (x < 0) sml += x * y;
else smr += x * y;
}
chmin(smr, mx);
vector<ll> dp(smr - sml + 1, -inf);
dp[0 - sml] = 0;
vector<vector<ll>> ans{dp};
for (auto [x, y] : B) {
int ax = abs(x);
vector<ll> memo;
vector<ll> res;
deque<pair<int, ll>> st;
rep (i, ax) {
// mod x ごとにスライド最大値の形になる
memo.clear();
for (int j = i; j <= smr - sml; j += ax) {
memo.push_back(dp[j]);
}
res.assign(memo.size(), -inf);
st.clear();
if (x > 0) {
rep (i, memo.size()) memo[i] -= i;
rep (i, res.size()) {
while (!st.empty() && st.front().first < i - y) st.pop_front();
while (!st.empty() && st.back().second < memo[i]) st.pop_back();
st.emplace_back(i, memo[i]);
res[i] = st.front().second + i;
}
}
else {
rep (i, memo.size()) memo[i] += i;
rrep (i, res.size()) {
while (!st.empty() && st.front().first > i + y) st.pop_front();
while (!st.empty() && st.back().second < memo[i]) st.pop_back();
st.emplace_back(i, memo[i]);
res[i] = st.front().second + i;
}
}
rep (j, res.size()) dp[j * ax + i] = res[j];
}
ans.push_back(dp);
}
reverse(all(ans));
return ans;
};
ll ans = -inf;
vector<ll> g(C.size() + 1);
rrep (i, C.size()) g[i] = gcd(g[i + 1], C[i].first);
vector<pair<int, ll>> D;
rrep (i, C.size()) D.emplace_back(C[i].first, min<ll>(C[i].second, M));
auto dp2 = calc_dp2(D, M * M * 2);
vector<vector<vector<int>>> js(C.size() - 1);
rep (m, C.size() - 1) {
ll sml2 = 0, smr2 = 0;
rep2 (j, m + 1, C.size()) {
ll x = C[m].first;
ll y = min<ll>(C[m].second, M);
if (x < 0) sml2 += x * y;
else smr2 += x * y;
}
sml2 = (sml2 % C[m].first + C[m].first) % C[m].first;
js[m].resize(C[m].first);
for (ll j = 0; j < dp2[m + 1].size(); j += g[m + 1]) {
if (dp2[m + 1][j] >= 0) js[m][(j + sml2) % C[m].first].push_back(j);
}
}
rep (i, smr - sml + 1) {
if (dp[i] < 0) continue;
ll L2 = L - (i + sml);
if (L2 % g[0]) continue;
ll sm = dp[i] + A[M];
int m = -1;
rep (j, C.size() - 1) {
ll tmp = C[j].second;
while ((L2 - tmp * C[j].first) % g[j + 1]) --tmp;
assert(tmp >= 0);
if ((L2 - tmp * C[j].first) / g[j + 1] < M * M) {
m = j;
break;
}
sm += tmp;
L2 -= tmp * C[j].first;
}
if (m == -1) {
assert(L2 % C.back().first == 0);
ll tmp = L2 / C.back().first;
if (tmp > C.back().second) continue;
sm += tmp;
chmax(ans, sm);
}
else {
ll sml2 = 0, smr2 = 0;
rep2 (j, m + 1, C.size()) {
ll x = C[m].first;
ll y = min<ll>(C[m].second, M);
if (x < 0) sml2 += x * y;
else smr2 += x * y;
}
auto itr = lower_bound(all(js[m][L2 % C[m].first]), L2 - sml2 - C[m].first * C[m].second) - js[m][L2 % C[m].first].begin();
for (int jk = itr; jk < js[m][L2 % C[m].first].size(); ++jk) {
ll j = js[m][L2 % C[m].first][jk];
if (j > smr2 - sml2) break;
ll L3 = L2 - (j + sml2);
if (L3 < 0) break;
ll sm2 = sm + dp2[m + 1][j];
assert(L3 % C[m].first == 0);
ll tmp = L3 / C[m].first;
sm2 += tmp;
chmax(ans, sm2);
break;
}
}
}
if (ans >= 0) {
cout << ans << endl;
}
else {
puts("impossible");
}
}
Compilation message
vault.cpp: In function 'int main()':
vault.cpp:199:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for (ll j = 0; j < dp2[m + 1].size(); j += g[m + 1]) {
| ~~^~~~~~~~~~~~~~~~~~~
vault.cpp:236:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
236 | for (int jk = itr; jk < js[m][L2 % C[m].first].size(); ++jk) {
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
0 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
