제출 #443276

#제출 시각아이디문제언어결과실행 시간메모리
443276JvThunder던전 (IOI21_dungeons)C++17
24 / 100
3404 ms2025404 KiB
#include "dungeons.h" #include <bits/stdc++.h> #define fir first #define sec second typedef long long ll; using namespace std; int N; vector<int> S,P,W,L; int base = 2; const int nop = 50; const int noa = 20; const int sz = 50005; ll jump[nop][noa][sz]; // 8^b,2^jump,pos ll add[nop][noa][sz]; ll diff[nop][noa][sz]; ll mx[nop][noa][sz]; 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; S.push_back(0); ll lim = 1; for(int bit=0;bit<nop;bit++) { for(int i=0;i<n;i++) { if(s[i]<lim) add[bit][0][i] = s[i], jump[bit][0][i] = w[i]; else add[bit][0][i] = p[i], jump[bit][0][i] = l[i]; diff[bit][0][i] = add[bit][0][i]-s[i]; mx[bit][0][i] = s[i]; } add[bit][0][n] = 0, jump[bit][0][n] = n, diff[bit][0][n] = 0, mx[bit][0][n] = 0; for(int i=1;i<noa;i++) { for(int j=0;j<=n;j++) { ll nxt = jump[bit][i-1][j]; add[bit][i][j] = add[bit][i-1][j] + add[bit][i-1][nxt]; diff[bit][i][j] = max(diff[bit][i-1][j], add[bit][i-1][j]+diff[bit][i-1][nxt]); mx[bit][i][j] = max(mx[bit][i-1][j],mx[bit][i-1][nxt]); jump[bit][i][j] = jump[bit][i-1][nxt]; } } lim *= base; } return; } ll simulate(int x, int z) { ll pos = x; ll str = z; ll lim = 1; ll phase = 0; while(pos!=N && phase<nop) { for(int i=noa-1;i>=0;i--) { //next stage if(str+diff[phase][i][pos]>=0 && mx[phase][i][pos]>=lim) continue; str += add[phase][i][pos]; pos = jump[phase][i][pos]; } if(pos==N) continue; if(str>=S[pos]) str += S[pos], pos = W[pos]; else str += P[pos], pos = L[pos]; phase++; lim *= base; } return str; }
#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...