| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 825290 | AbdelmagedNour | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#include "dungeons.h"
typedef long long ll;
const int N=50005;
struct Node{
int person=0;
ll op=LLONG_MIN,gained=0;
}dp[N][24][24];
int _n;
Node Merge(Node a,Node b){
Node res;
res.person=b.person;
res.gained=a.gained+b.gained;
res.op=max({1LL*a.op,b.op+a.gained});
return res;
}
vector<int>_s,_p,_w,_l;
void init(int n,vector<int>s,vector<int>p,vector<int>w,vector<int>l){
_n=n;
_s=s,_p=p,_w=w,_l=l;
for(int i=0;i<n;i++){
for(int j=0;j<24;j++){
for(int k=0;k<24;k++){
if(s[i]>=(1<<k))dp[i][j][k]={l[i],-s[i],p[i]};
else dp[i][j][k]={w[i],LLONG_MIN,s[i]};
}
}
}
for(int j=0;j<24;j++){
for(int k=0;k<24;k++){
dp[n][j][k]={n,0,0};
}
}
for(int j=1;j<24;j++)for(int i=0;i<n;i++){
for(int k=0;k<24;k++){
dp[i][j][k]=Merge(dp[i][j-1][k],dp[dp[i][j-1][k].person][j-1][k]);
}
}
return;
}
long long simulate(int x,ll z){
while(x!=_n){
int k=__lg(z);
if(z>=_s[x]&&_s[x]>=(1LL<<k)){
z+=_s[x];
x=_w[x];
continue;
}
for(int j=23;j>=0;j--){
if(z+dp[x][j][k].op<0){
z+=dp[x][j][k].gained;
x=dp[x][j][k].person;
}
}
if(z>=_s[x]&&_s[x]>=(1LL<<k)){
z+=_s[x];
x=_w[x];
}
}
return z;
}