| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 825290 | AbdelmagedNour | Dungeons Game (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}