Submission #826582

#TimeUsernameProblemLanguageResultExecution timeMemory
826582arnold518Dungeons Game (IOI21_dungeons)C++17
100 / 100
2136 ms1439060 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 4e5; const ll INF = 1e18; int N; int S[MAXN+10], P[MAXN+10], W[MAXN+10], L[MAXN+10]; vector<vector<int>> A, B, C; ll D[MAXN+10]; int f(int i, int j) { return i*(i+1)/2+j; } void init(int _N, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L) { N=_N; for(int i=1; i<=N; i++) { S[i]=_S[i-1]; P[i]=_P[i-1]; W[i]=_W[i-1]+1; L[i]=_L[i-1]+1; } A=vector<vector<int>>(300, vector<int>(N+2)); B=vector<vector<int>>(300, vector<int>(N+2)); C=vector<vector<int>>(300, vector<int>(N+2)); for(int i=0; i<=23; i++) { int p=f(i, 0); for(int j=1; j<=N; j++) { if(S[j]<(1<<i)) A[p][j]=S[j], B[p][j]=(1<<(i+1)), C[p][j]=W[j]; else if(S[j]<(1<<(i+1))) A[p][j]=P[j], B[p][j]=min((1<<(i+1)), S[j]), C[p][j]=L[j]; else A[p][j]=P[j], B[p][j]=(1<<(i+1)), C[p][j]=L[j]; } A[p][N+1]=0, B[p][N+1]=0; C[p][N+1]=N+1; for(int j=1; j<=i; j++) { p=f(i, j); for(int k=1; k<=N+1; k++) { C[p][k]=C[p-1][C[p-1][k]]; A[p][k]=A[p-1][k]+A[p-1][C[p-1][k]]; B[p][k]=min(B[p-1][k], B[p-1][C[p-1][k]]-A[p-1][k]); } } } for(int i=N; i>=0; i--) D[i]=D[W[i]]+S[i]; } ll simulate(int now, int _x) { now++; ll x=_x; for(int i=0; i<=23; i++) { if(x>=(1<<(i+1))) continue; for(int j=i; j>=0; j--) { int p=f(i, j); if(x<B[p][now]) { x+=A[p][now]; now=C[p][now]; } } if(now>N) break; if(x<(1<<(i+1))) { if(x>=S[now]) x+=S[now], now=W[now]; else x+=P[now], now=L[now]; } } return x+D[now]; }
#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...