제출 #972927

#제출 시각아이디문제언어결과실행 시간메모리
972927NemanjaSo2005던전 (IOI21_dungeons)C++17
63 / 100
3604 ms1300792 KiB
#include "dungeons.h" #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=4e5+5; const int maxl=25; const int baza=8; int N,step[10],potrebno[maxn]; ll dobija[maxn]; int koji[maxn][baza+2][maxl+2],suma[maxn][baza+2][maxl+2],gubit[maxn][baza+2][maxl+2]; vector<int> S,P,W,L; void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l){ S=s; P=p; W=w; L=l; N=n; potrebno[N]=1; dobija[N]=0; for(int i=N-1;i>=0;i--){ potrebno[i]=max(s[i],potrebno[w[i]]-s[i]); dobija[i]=dobija[w[i]]+s[i]; } step[0]=1; for(int i=1;i<=baza;i++) step[i]=step[i-1]*baza; for(int b=0;b<baza;b++){ for(int i=0;i<N;i++) if(s[i]<=step[b]){ koji[i][b][0]=w[i]; suma[i][b][0]=s[i]; gubit[i][b][0]=1e9; } else{ koji[i][b][0]=l[i]; suma[i][b][0]=p[i]; gubit[i][b][0]=s[i]; } for(int j=1;j<=maxl;j++) for(int i=1;i<=N;i++){ int sl=koji[i][b][j-1]; koji[i][b][j]=koji[sl][b][j-1]; suma[i][b][j]=min(20'000'000,suma[i][b][j-1]+suma[sl][b][j-1]); gubit[i][b][j]=min(gubit[i][b][j-1],gubit[sl][b][j-1]-suma[i][b][j-1]); } } } ll simulate(int poz,int snaga){ if(potrebno[poz]<=snaga) return snaga+dobija[poz]; int b=baza-1; while(step[b]>snaga) b--; for(int i=maxl;i>=0;i--) if(gubit[poz][b][i]>snaga){ snaga+=suma[poz][b][i]; poz=koji[poz][b][i]; } for(int it=1;it<=5;it++){ if(poz==N) break; if(snaga>=S[poz]){ snaga+=S[poz]; poz=W[poz]; } else{ snaga+=P[poz]; poz=L[poz]; } } return simulate(poz,snaga); }
#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...