oj.uz

Submission #972927

# Submission time Handle Problem Language Result Execution time Memory
972927 2024-05-01T10:27:24 Z NemanjaSo2005 Dungeons Game (IOI21_dungeons) C++17
63 / 100
 3604 ms 1300792 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=4e5+5;
const int maxl=25;
const int baza=8;
int N,step[10],potrebno[maxn];
ll dobija[maxn];
int koji[maxn][baza+2][maxl+2],suma[maxn][baza+2][maxl+2],gubit[maxn][baza+2][maxl+2];
vector<int> S,P,W,L;
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;
   potrebno[N]=1;
   dobija[N]=0;
   for(int i=N-1;i>=0;i--){
      potrebno[i]=max(s[i],potrebno[w[i]]-s[i]);
      dobija[i]=dobija[w[i]]+s[i];
   }

   step[0]=1;
   for(int i=1;i<=baza;i++)
      step[i]=step[i-1]*baza;
   for(int b=0;b<baza;b++){
      for(int i=0;i<N;i++)
         if(s[i]<=step[b]){
            koji[i][b][0]=w[i];
            suma[i][b][0]=s[i];
            gubit[i][b][0]=1e9;
         }
         else{
            koji[i][b][0]=l[i];
            suma[i][b][0]=p[i];
            gubit[i][b][0]=s[i];
         }
      for(int j=1;j<=maxl;j++)
         for(int i=1;i<=N;i++){
            int sl=koji[i][b][j-1];
            koji[i][b][j]=koji[sl][b][j-1];
            suma[i][b][j]=min(20'000'000,suma[i][b][j-1]+suma[sl][b][j-1]);
            gubit[i][b][j]=min(gubit[i][b][j-1],gubit[sl][b][j-1]-suma[i][b][j-1]);
         }
   }
}

ll simulate(int poz,int snaga){
   if(potrebno[poz]<=snaga)
      return snaga+dobija[poz];
   int b=baza-1;
   while(step[b]>snaga)
      b--;
   for(int i=maxl;i>=0;i--)
      if(gubit[poz][b][i]>snaga){
         snaga+=suma[poz][b][i];
         poz=koji[poz][b][i];
      }
   for(int it=1;it<=5;it++){
      if(poz==N)
         break;
      if(snaga>=S[poz]){
         snaga+=S[poz];
         poz=W[poz];
      }
      else{
         snaga+=P[poz];
         poz=L[poz];
      }
   }
   return simulate(poz,snaga);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 238 ms 172244 KB Output is correct
5 Correct 6 ms 14940 KB Output is correct
6 Correct 231 ms 171968 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3604 ms 1295644 KB Output is correct
3 Correct 3590 ms 1299768 KB Output is correct
4 Incorrect 3427 ms 1300792 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14944 KB Output is correct
2 Correct 254 ms 175560 KB Output is correct
3 Correct 214 ms 175680 KB Output is correct
4 Correct 199 ms 175240 KB Output is correct
5 Correct 192 ms 174988 KB Output is correct
6 Correct 238 ms 175184 KB Output is correct
7 Correct 244 ms 175188 KB Output is correct
8 Correct 206 ms 174932 KB Output is correct
9 Correct 206 ms 175184 KB Output is correct
10 Correct 182 ms 174944 KB Output is correct
11 Correct 372 ms 175440 KB Output is correct
12 Correct 691 ms 175324 KB Output is correct
13 Correct 521 ms 175136 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14944 KB Output is correct
2 Correct 254 ms 175560 KB Output is correct
3 Correct 214 ms 175680 KB Output is correct
4 Correct 199 ms 175240 KB Output is correct
5 Correct 192 ms 174988 KB Output is correct
6 Correct 238 ms 175184 KB Output is correct
7 Correct 244 ms 175188 KB Output is correct
8 Correct 206 ms 174932 KB Output is correct
9 Correct 206 ms 175184 KB Output is correct
10 Correct 182 ms 174944 KB Output is correct
11 Correct 372 ms 175440 KB Output is correct
12 Correct 691 ms 175324 KB Output is correct
13 Correct 521 ms 175136 KB Output is correct
14 Correct 4 ms 14944 KB Output is correct
15 Correct 228 ms 175456 KB Output is correct
16 Correct 262 ms 175576 KB Output is correct
17 Correct 214 ms 175168 KB Output is correct
18 Correct 214 ms 175188 KB Output is correct
19 Correct 256 ms 175188 KB Output is correct
20 Correct 237 ms 175068 KB Output is correct
21 Correct 254 ms 172876 KB Output is correct
22 Correct 247 ms 172884 KB Output is correct
23 Correct 417 ms 173252 KB Output is correct
24 Correct 435 ms 175324 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14944 KB Output is correct
2 Correct 254 ms 175560 KB Output is correct
3 Correct 214 ms 175680 KB Output is correct
4 Correct 199 ms 175240 KB Output is correct
5 Correct 192 ms 174988 KB Output is correct
6 Correct 238 ms 175184 KB Output is correct
7 Correct 244 ms 175188 KB Output is correct
8 Correct 206 ms 174932 KB Output is correct
9 Correct 206 ms 175184 KB Output is correct
10 Correct 182 ms 174944 KB Output is correct
11 Correct 372 ms 175440 KB Output is correct
12 Correct 691 ms 175324 KB Output is correct
13 Correct 521 ms 175136 KB Output is correct
14 Correct 4 ms 14944 KB Output is correct
15 Correct 228 ms 175456 KB Output is correct
16 Correct 262 ms 175576 KB Output is correct
17 Correct 214 ms 175168 KB Output is correct
18 Correct 214 ms 175188 KB Output is correct
19 Correct 256 ms 175188 KB Output is correct
20 Correct 237 ms 175068 KB Output is correct
21 Correct 254 ms 172876 KB Output is correct
22 Correct 247 ms 172884 KB Output is correct
23 Correct 417 ms 173252 KB Output is correct
24 Correct 435 ms 175324 KB Output is correct
25 Correct 216 ms 173944 KB Output is correct
26 Correct 277 ms 173636 KB Output is correct
27 Correct 241 ms 172996 KB Output is correct
28 Correct 290 ms 172992 KB Output is correct
29 Correct 303 ms 173512 KB Output is correct
30 Correct 261 ms 173248 KB Output is correct
31 Correct 267 ms 172888 KB Output is correct
32 Correct 477 ms 173020 KB Output is correct
33 Correct 387 ms 175324 KB Output is correct
34 Correct 766 ms 172916 KB Output is correct
35 Correct 472 ms 173120 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3604 ms 1295644 KB Output is correct
3 Correct 3590 ms 1299768 KB Output is correct
4 Incorrect 3427 ms 1300792 KB Output isn't correct
5 Halted 0 ms 0 KB -