Submission #921300

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
9213002024-02-03 16:41:55byunjaewooDungeons Game (IOI21_dungeons)C++17
63 / 100
4868 ms2097152 KiB
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int Nmax=400001;
int N, S[Nmax], P[Nmax], W[Nmax], L[Nmax];
ll DP[Nmax];
vector<int> nxt[24][Nmax], mx[24][Nmax], sum[24][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<N; i++) S[i]=S_[i], P[i]=P_[i], W[i]=W_[i], L[i]=L_[i];
for(int i=1; i<24; i++) {
for(int j=0; j<N; j++) {
nxt[i][j].emplace_back(0); sum[i][j].emplace_back(0); mx[i][j].emplace_back(0);
if(S[j]>=(1<<(i+1))) nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=(1<<(i+1))-1-P[j];
else if(S[j]<=(1<<i)) nxt[i][j][0]=W[j], sum[i][j][0]=S[j], mx[i][j][0]=(1<<(i+1))-1-S[j];
else nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=std::min(S[j]-1, (1<<(i+1))-1-P[j]);
}
nxt[i][N].emplace_back(0); sum[i][N].emplace_back(0); mx[i][N].emplace_back(0);
nxt[i][N][0]=N, sum[i][N][0]=0, mx[i][N][0]=(1<<(i+1))-1;
for(int j=1; j<i; j++) for(int k=0; k<=N; k++) {
nxt[i][k].emplace_back(0); sum[i][k].emplace_back(0); mx[i][k].emplace_back(0);
nxt[i][k][j]=nxt[i][nxt[i][k][j-1]][j-1];
sum[i][k][j]=min(sum[i][k][j-1]+sum[i][nxt[i][k][j-1]][j-1], 1000000000);
mx[i][k][j]=min(mx[i][k][j-1], mx[i][nxt[i][k][j-1]][j-1]-sum[i][k][j-1]);
}
}
for(int i=N-1; i>=0; i--) DP[i]=DP[W[i]]+S[i];
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#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...