Submission #927508

#TimeUsernameProblemLanguageResultExecution timeMemory
927508math_rabbit_1028Uplifting Excursion (BOI22_vault)C++14
100 / 100
3615 ms2220 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef pair<int, int> pii; typedef long long ll; int M, K; ll L, S, arr[1010], rem[1010], ans; int dp[2][202020]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> M >> L; K = 2*M*M; for (int i = 0; i <= 2*M; i++) cin >> arr[i]; for (int i = 0; i <= 2*M; i++) S += (i-M)*arr[i]; if (S < L) { L = -L; for (int i = 0; i <= M; i++) swap(arr[i], arr[2*M-i]); } S = 0; for (int i = 0; i <= M; i++) { S += (i-M)*arr[i]; ans += arr[i]; rem[2*M-i] = arr[i]; arr[i] = 0; } if (S > L) { cout << "impossible\n"; return 0; } for (int i = M+1; i <= 2*M; i++) { ll t = (L-S)/(i-M); if (t >= arr[i]) { ans += arr[i]; rem[2*M-i] = arr[i]; S += arr[i]*(i-M); arr[i] = 0; } else { ans += t; rem[2*M-i] = t; S += t*(i-M); arr[i] -= t; break; } } for (int j = 0; j <= K; j++) dp[0][j] = -1e9; dp[0][M*M] = 0; for (int i = 1; i <= M; i++) { for (int r = 0; r < i; r++) { deque< pair<int, int> > dq1, dq2; for (int j = r; j <= K; j += i) { while (dq1.size() > 0 && (j-dq1.front().fi)/i > arr[M+i]) dq1.pop_front(); while (dq1.size() > 0 && dq1.back().se + (j-dq1.back().fi)/i <= dp[0][j]) dq1.pop_back(); dq1.push_back({j, dp[0][j]}); while (dq2.size() > 0 && (j-dq2.front().fi)/i > rem[M+i]) dq2.pop_front(); while (dq2.size() > 0 && dq2.back().se - (j-dq2.back().fi)/i <= dp[0][j]) dq2.pop_back(); dq2.push_back({j, dp[0][j]}); dp[1][j] = max(dq1.front().se + (j-dq1.front().fi)/i, dq2.front().se - (j-dq2.front().fi)/i); } } for (int j = 0; j <= K; j++) dp[0][j] = dp[1][j]; } for (int i = M+1; i <= 2*M; i++) { for (int r = 0; r < i-M; r++) { deque< pair<int, int> > dq; int j = r; while (j+i-M <= K) j += i-M; for (; j >= r; j -= i-M) { while (dq.size() > 0 && (dq.front().fi-j)/(i-M) > arr[2*M-i]) dq.pop_front(); while (dq.size() > 0 && dq.back().se + (dq.back().fi-j)/(i-M) <= dp[0][j]) dq.pop_back(); dq.push_back({j, dp[0][j]}); dp[1][j] = dq.front().se + (dq.front().fi-j)/(i-M); } } for (int r = 0; r < i-M; r++) { deque< pair<int, int> > dq; int j = r; while (j+i-M <= K) j += i-M; for (; j >= r; j -= i-M) { while (dq.size() > 0 && (dq.front().fi-j)/(i-M) > rem[2*M-i]) dq.pop_front(); while (dq.size() > 0 && dq.back().se - (dq.back().fi-j)/(i-M) <= dp[0][j]) dq.pop_back(); dq.push_back({j, dp[0][j]}); dp[1][j] = max(dp[1][j], dq.front().se - (dq.front().fi-j)/(i-M)); } } for (int j = 0; j <= K; j++) dp[0][j] = dp[1][j]; } if (dp[0][L-S+M*M] <= -1e8) cout << "impossible\n"; else cout << ans + dp[0][L-S+M*M] << "\n"; return 0; }
#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...