Submission #1231366

#TimeUsernameProblemLanguageResultExecution timeMemory
1231366omsincoconutUplifting Excursion (BOI22_vault)C++17
0 / 100
175 ms588 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18, BOUND = 10000; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll M, L; cin >> M >> L; ll A[2*M+1]; for (ll i = 0; i <= 2*M; i++) cin >> A[i]; ll sum = 0, cnt = 0; for (ll i = 0; i <= 2*M; i++) sum += (i-M)*A[i], cnt += A[i]; if (sum < L) { cout << "impossible"; return 0; } else if (L == 0) { cout << A[0]; return 0; } ll idx = -1, take = -1; for (ll i = 2*M; i >= M+1; i--) { if (sum-(i-M)*A[i] > L) { sum -= (i-M)*A[i]; cnt -= A[i]; } else { idx = i-M; take = (sum-L)/(i-M); sum -= (i-M)*take; cnt -= take; } } ll knap_min[BOUND]; fill(knap_min, knap_min+BOUND, INF); knap_min[0] = 0; for (ll i = 1; i < idx; i++) { for (ll j = BOUND-1; j >= 0; j--) { for (ll k = 1; j-i*k >= 0 && k <= A[M+i]; k++) { knap_min[j] = min(knap_min[j], knap_min[j-i*k]+k); } } } for (ll j = BOUND-1; j >= 0; j--) { for (ll k = 1; j-idx*k >= 0 && k <= A[M+idx]-take; k++) { knap_min[j] = min(knap_min[j], knap_min[j-idx*k]+k); } } ll knap_max[BOUND]; fill(knap_max, knap_max+BOUND, -INF); knap_max[0] = 0; for (ll i = idx+1; i <= M; i++) { for (ll j = BOUND-1; j >= 0; j--) { for (ll k = 1; j-i*k >= 0 && k <= A[M+i]; k++) { knap_max[j] = max(knap_max[j], knap_max[j-i*k]+k); } } } for (ll j = BOUND-1; j >= 0; j--) { for (ll k = 1; j-idx*k >= 0 && k <= take; k++) { knap_max[j] = max(knap_max[j], knap_max[j-idx*k]+k); } } ll goal = sum-L, ans = -INF; for (ll i = goal; i < BOUND; i++) { ans = max(ans, cnt-knap_min[i]+knap_max[i-goal]); } if (ans == -INF) cout << "impossible"; else cout << ans; return 0; } /* 1 5 0 0 6 */
#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...