This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
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;
rep (i, 2 * M + 1) {
if (i == M) continue;
if (A[i] == 0) continue;
// if (A[i] > M) continue;
B.emplace_back(i - M, A[i]);
}
vector<ll> dp(smr - sml + 1, -inf);
dp[0 - sml] = 0;
for (auto [x, y] : B) {
int ax = abs(x);
rep (i, ax) {
// mod x ごとにスライド最大値の形になる
vector<ll> memo;
for (int j = i; j <= smr - sml; j += ax) {
memo.push_back(dp[j]);
}
vector<ll> res(memo.size(), -inf);
deque<int> st;
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];
}
}
if (dp[L - sml] >= 0) {
cout << dp[L - sml] + A[M] << endl;
}
else {
puts("impossible");
}
}
# | 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... |