제출 #927523

#제출 시각아이디문제언어결과실행 시간메모리
927523math_rabbit_1028Uplifting Excursion (BOI22_vault)C++14
100 / 100
3262 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); } } memcpy(dp[0], dp[1], sizeof(int)*(K+1)); //for (int j = 0; j <= K; j++) dp[0][j] = dp[1][j]; } for (int i = 1; i <= M; i++) { for (int r = 0; r < i; r++) { deque< pair<int, int> > dq1, dq2; int j = r; while (j+i <= K) j += i; for (; j >= r; j -= i) { while (dq1.size() > 0 && (dq1.front().fi-j)/i > arr[M-i]) dq1.pop_front(); while (dq1.size() > 0 && dq1.back().se + (dq1.back().fi-j)/i <= dp[0][j]) dq1.pop_back(); dq1.push_back({j, dp[0][j]}); while (dq2.size() > 0 && (dq2.front().fi-j)/i > rem[M-i]) dq2.pop_front(); while (dq2.size() > 0 && dq2.back().se - (dq2.back().fi-j)/i <= dp[0][j]) dq2.pop_back(); dq2.push_back({j, dp[0][j]}); dp[1][j] = max(dq1.front().se + (dq1.front().fi-j)/i, dq2.front().se - (dq2.front().fi-j)/i); } } memcpy(dp[0], dp[1], sizeof(int)*(K+1)); //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...