Submission #1049897

#TimeUsernameProblemLanguageResultExecution timeMemory
1049897shiomusubi496Uplifting Excursion (BOI22_vault)C++17
0 / 100
2 ms604 KiB
#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; vector<pair<int, ll>> C; rep (i, 2 * M + 1) { if (i == M) continue; if (A[i] == 0) continue; if (A[i] <= M) B.emplace_back(i - M, A[i]); else C.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); 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]; } } 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 + lo || i + hi < L) continue; if ((L - i) % x) continue; chmax(ans, dp[i] + A[M] + abs((L - i) / x)); } if (ans >= 0) { cout << ans << endl; } else { puts("impossible"); } return 0; } else { assert(false); // hoge } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...