Submission #927483

#TimeUsernameProblemLanguageResultExecution timeMemory
927483math_rabbit_1028Uplifting Excursion (BOI22_vault)C++14
0 / 100
2 ms16732 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<int, 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(); dp[i][j] = max(dp[i-1][j], dq.front().se + (j-dq.front().fi)/i); while (dq.size() > 0 && dq.back().se + (j-dq.back().fi)/i <= dp[i][j]) dq.pop_back(); dq.push_back({j, dp[i][j]}); } } for (int j = 0; j <= 2*M*M; j++) { for (int k = 0; k <= rem[M+i]; k++) { if (j-i*k < 0) break; dp[i][j] = max(dp[i][j], dp[i-1][j-i*k]-k); } } } for (int i = M+1; i <= 2*M; i++) { for (int j = 0; j <= 2*M*M; j++) { dp[i][j] = -1e18; for (int k = 0; k <= arr[2*M-i]; k++) { if (j+(i-M)*k > 2*M*M) break; dp[i][j] = max(dp[i][j], dp[i-1][j+(i-M)*k]+k); } for (int k = 0; k <= rem[2*M-i]; k++) { if (j+(i-M)*k > 2*M*M) break; dp[i][j] = max(dp[i][j], dp[i-1][j+(i-M)*k]-k); } } } 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...