Submission #653525

#TimeUsernameProblemLanguageResultExecution timeMemory
653525ertoUplifting Excursion (BOI22_vault)C++17
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> typedef long long int ll; typedef long double ld; #define INF (int)(1e9 + 7) #define INF2 998244353 #define N (ll)(3e2 + 5) //#define f first //#define s second #define int ll #define lsb(x) (x & (-x)) using namespace std; int n, m, g, h, l; int a[1000]; int dp1[100000], dp2[100000]; int cnt1[100000], cnt2[100000]; int sum = 0; int f1(int x){ int sum = 0; while(x){ sum += cnt1[x]; x -= cnt1[x] * dp1[x]; } return sum; } int f2(int x){ int sum = 0; while(x){ sum += cnt2[x]; x -= cnt2[x] * dp2[x]; } return sum; } void solve(){ cin >> m >> l; for(int i=0; i<2*m+1; i++){ cin >> a[i]; if(i > m){ sum += (i - m) * a[i]; } } int ans = a[m]; int cur = 0; int t1, t2; dp1[0] = dp2[0] = 1; if(sum < l){ cout << "IMPOSSIBLE"; return; } bool bb = 0; for(int i=m+1; i<=2*m; i++){ g = (l - cur) / (i - m); h = min(g, a[i]); ans += h; cur += h * (i - m); t1 = h; t2 = a[i] - h; if(cur == l)break; for(int k=99000; k; k--){ if(dp1[k])continue; for(int j=1; j<=t1 && j * (i - m) <= k; j++){ if(dp1[k - j * (i - m)]){ dp1[k] = (i - m); cnt1[k] = j; } } } for(int k=99000; k; k--){ if(dp2[k])continue; for(int j=1; j<=t2 && j * (i - m) <= k; j++){ if(dp2[k - j * (i - m)]){ dp2[k] = (i - m); cnt2[k] = j; } } } int dif = l - cur; for(int j=dif; j<=99000; j++){ if(dp2[j] > 0 && dp1[j - dif] > 0){ bb = 1; ans -= f1(j - dif); ans += f2(j); } } if(bb)break; } if(!bb){ cout << "IMPOSSIBLE"; return; } cout << ans; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int T = 1; //cin>>T; for(int i=1; i<=T; i++){ solve(); } }
#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...