제출 #921219

#제출 시각아이디문제언어결과실행 시간메모리
921219byunjaewoo던전 (IOI21_dungeons)C++17
0 / 100
49 ms306004 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; using ll=long long; const int Nmax=50010; int N; ll nxt[25][25][Nmax], sum[25][25][Nmax], mx[25][25][Nmax]; 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<25; i++) { for(int j=0; j<N; j++) { if(S[j]>=(1<<(i+1))) nxt[i][0][j]=L[j], sum[i][0][j]=P[j], mx[i][0][j]=(1<<(i+1))-1; else if(S[j]<=(1<<i)) nxt[i][0][j]=W[j], sum[i][0][j]=S[j], mx[i][0][j]=(1<<(i+1))-1; else nxt[i][0][j]=L[j], sum[i][0][j]=P[j], mx[i][0][j]=S[j]; } nxt[i][0][N]=N, sum[i][0][N]=0, mx[i][0][N]=(1<<(i+1))-1; for(int j=1; j<25; j++) for(int k=0; k<=N; k++) { nxt[i][j][k]=nxt[i][j-1][nxt[i][j-1][k]]; sum[i][j][k]=sum[i][j-1][k]+sum[i][j-1][nxt[i][j-1][k]]; mx[i][j][k]=min(mx[i][j-1][k], mx[i][j-1][nxt[i][j-1][k]]-sum[i][j-1][nxt[i][j-1][k]]); } } } long long simulate(int x, int z) { int k=x; ll v=z; for(int i=0; i<25; i++) { int kk=k; ll vv=v; for(int j=24; j>=0; j--) if(vv<=mx[i][j][kk]) vv+=sum[i][j][kk], kk=nxt[i][j][kk]; if(vv<=mx[i][0][kk]) vv+=sum[i][0][kk], kk=nxt[i][0][kk]; if(kk==N) { for(int j=24; j>=0; j--) if(nxt[i][j][k]!=N) v+=sum[i][j][k], k=nxt[i][j][k]; if(k!=N) v+=sum[i][0][k], k=nxt[i][0][k]; return v; } k=kk, v=vv; } return 0; }
#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...