Submission #927497

#TimeUsernameProblemLanguageResultExecution timeMemory
927497math_rabbit_1028Uplifting Excursion (BOI22_vault)C++14
80 / 100
4153 ms477100 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; ll L, S, arr[1010], rem[1010], ans; ll dp[660][101010]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> M >> L; 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 <= 2*M*M; j++) dp[0][j] = -1e18; dp[0][M*M] = 0; for (int i = 1; i <= M; i++) { for (int r = 0; r < i; r++) { deque< pair<ll, ll> > dq; for (int j = r; j <= 2*M*M; j += i) { while (dq.size() > 0 && (j-dq.front().fi)/i > arr[M+i]) dq.pop_front(); while (dq.size() > 0 && dq.back().se + (j-dq.back().fi)/i <= dp[i-1][j]) dq.pop_back(); dq.push_back({j, dp[i-1][j]}); dp[i][j] = dq.front().se + (j-dq.front().fi)/i; } } for (int r = 0; r < i; r++) { deque< pair<ll, ll> > dq; for (int j = r; j <= 2*M*M; j += i) { while (dq.size() > 0 && (j-dq.front().fi)/i > rem[M+i]) dq.pop_front(); while (dq.size() > 0 && dq.back().se - (j-dq.back().fi)/i <= dp[i-1][j]) dq.pop_back(); dq.push_back({j, dp[i-1][j]}); dp[i][j] = max(dp[i][j], dq.front().se - (j-dq.front().fi)/i); } } } for (int i = M+1; i <= 2*M; i++) { for (int r = 0; r < i-M; r++) { deque< pair<ll, ll> > dq; int j = r; while (j+i-M <= 2*M*M) 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[i-1][j]) dq.pop_back(); dq.push_back({j, dp[i-1][j]}); dp[i][j] = dq.front().se + (dq.front().fi-j)/(i-M); } } for (int r = 0; r < i-M; r++) { deque< pair<ll, ll> > dq; int j = r; while (j+i-M <= 2*M*M) 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[i-1][j]) dq.pop_back(); dq.push_back({j, dp[i-1][j]}); dp[i][j] = max(dp[i][j], dq.front().se - (dq.front().fi-j)/(i-M)); } } } if (dp[2*M][L-S+M*M] <= -1e17) cout << "impossible\n"; else cout << ans + dp[2*M][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...