Submission #623353

#TimeUsernameProblemLanguageResultExecution timeMemory
623353tinjyuDungeons Game (IOI21_dungeons)C++17
11 / 100
7093 ms239108 KiB
#include "dungeons.h" #include <vector> #include <iostream> using namespace std; long long int n,s[1000005],p[1000005],l[1000005],w[1000005]; long long int step[400005][25][8]; long long int d[400005][25][8]; long long int mx[400005][25][8]; void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) { n=N; for(int i=0;i<n;i++)s[i]=S[i]; for(int i=0;i<n;i++)p[i]=P[i]; for(int i=0;i<n;i++)w[i]=W[i]; for(int i=0;i<n;i++)l[i]=L[i]; long long int b=1; for(int bits=0;bits<25;bits++) { for(int i=0;i<n;i++) { if(s[i]>b) { step[i][bits][0]=l[i]; mx[i][bits][0]=s[i]; d[i][bits][0]=p[i]; } else { step[i][bits][0]=W[i]; mx[i][bits][0]=1e18; d[i][bits][0]=S[i]; } } for(int len=1;len<8;len++) { for(int i=0;i<n;i++) { long long int ti=8,now=i; while(ti--) { if(now==n)break; mx[i][bits][len]=min(mx[i][bits][len],mx[now][bits][len-1]-d[i][bits][len]); d[i][bits][len]+=d[now][bits][len-1]; step[i][bits][len]=step[now][bits][len-1]; now=step[i][bits][len]; } } } b*=2; } return; } long long simulate(int x, int z) { int now=x; int b=1; for(int bits=0;bits<25;bits++) { if(b*2<z) { b*=2; continue; } for(int len=7;len>=0;len--) { while(z<mx[now][bits][len]) { z+=d[now][bits][len]; now=step[now][bits][len]; if(now==n)break; } if(now==n)break; } if(now==n)break; z+=s[now]; now=w[now]; if(now==n)break; b*=2; } return z; }
#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...