oj.uz

답안 #972936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972936 2024-05-01T10:30:49 Z NemanjaSo2005 던전 (IOI21_dungeons) C++17
63 / 100
 3764 ms 1301324 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 s){
   ll snaga=s;
   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];
      }
   }
   if(potrebno[poz]<=snaga)
      return snaga+dobija[poz];
   return simulate(poz,snaga);
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 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 281 ms 174096 KB Output is correct
5 Correct 7 ms 14936 KB Output is correct
6 Correct 233 ms 174140 KB Output is correct

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3764 ms 1299468 KB Output is correct
3 Correct 3508 ms 1299836 KB Output is correct
4 Incorrect 3359 ms 1301324 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 251 ms 175584 KB Output is correct
3 Correct 191 ms 175676 KB Output is correct
4 Correct 176 ms 175200 KB Output is correct
5 Correct 192 ms 174936 KB Output is correct
6 Correct 240 ms 175188 KB Output is correct
7 Correct 274 ms 175324 KB Output is correct
8 Correct 204 ms 174940 KB Output is correct
9 Correct 196 ms 175072 KB Output is correct
10 Correct 194 ms 174948 KB Output is correct
11 Correct 362 ms 175192 KB Output is correct
12 Correct 744 ms 175440 KB Output is correct
13 Correct 531 ms 175308 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 251 ms 175584 KB Output is correct
3 Correct 191 ms 175676 KB Output is correct
4 Correct 176 ms 175200 KB Output is correct
5 Correct 192 ms 174936 KB Output is correct
6 Correct 240 ms 175188 KB Output is correct
7 Correct 274 ms 175324 KB Output is correct
8 Correct 204 ms 174940 KB Output is correct
9 Correct 196 ms 175072 KB Output is correct
10 Correct 194 ms 174948 KB Output is correct
11 Correct 362 ms 175192 KB Output is correct
12 Correct 744 ms 175440 KB Output is correct
13 Correct 531 ms 175308 KB Output is correct
14 Correct 4 ms 14940 KB Output is correct
15 Correct 245 ms 175460 KB Output is correct
16 Correct 251 ms 175584 KB Output is correct
17 Correct 182 ms 175168 KB Output is correct
18 Correct 200 ms 175180 KB Output is correct
19 Correct 258 ms 175448 KB Output is correct
20 Correct 218 ms 174932 KB Output is correct
21 Correct 207 ms 175200 KB Output is correct
22 Correct 222 ms 175200 KB Output is correct
23 Correct 382 ms 175320 KB Output is correct
24 Correct 438 ms 175496 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 251 ms 175584 KB Output is correct
3 Correct 191 ms 175676 KB Output is correct
4 Correct 176 ms 175200 KB Output is correct
5 Correct 192 ms 174936 KB Output is correct
6 Correct 240 ms 175188 KB Output is correct
7 Correct 274 ms 175324 KB Output is correct
8 Correct 204 ms 174940 KB Output is correct
9 Correct 196 ms 175072 KB Output is correct
10 Correct 194 ms 174948 KB Output is correct
11 Correct 362 ms 175192 KB Output is correct
12 Correct 744 ms 175440 KB Output is correct
13 Correct 531 ms 175308 KB Output is correct
14 Correct 4 ms 14940 KB Output is correct
15 Correct 245 ms 175460 KB Output is correct
16 Correct 251 ms 175584 KB Output is correct
17 Correct 182 ms 175168 KB Output is correct
18 Correct 200 ms 175180 KB Output is correct
19 Correct 258 ms 175448 KB Output is correct
20 Correct 218 ms 174932 KB Output is correct
21 Correct 207 ms 175200 KB Output is correct
22 Correct 222 ms 175200 KB Output is correct
23 Correct 382 ms 175320 KB Output is correct
24 Correct 438 ms 175496 KB Output is correct
25 Correct 232 ms 174644 KB Output is correct
26 Correct 257 ms 175580 KB Output is correct
27 Correct 208 ms 174932 KB Output is correct
28 Correct 204 ms 175312 KB Output is correct
29 Correct 277 ms 175580 KB Output is correct
30 Correct 230 ms 175328 KB Output is correct
31 Correct 236 ms 174928 KB Output is correct
32 Correct 442 ms 175440 KB Output is correct
33 Correct 320 ms 175184 KB Output is correct
34 Correct 617 ms 175200 KB Output is correct
35 Correct 388 ms 175196 KB Output is correct

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3764 ms 1299468 KB Output is correct
3 Correct 3508 ms 1299836 KB Output is correct
4 Incorrect 3359 ms 1301324 KB Output isn't correct
5 Halted 0 ms 0 KB -