oj.uz

답안 #972925

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972925 2024-05-01T10:26:14 Z NemanjaSo2005 던전 (IOI21_dungeons) C++17
63 / 100
 3459 ms 1089928 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=4e5+5;
const int maxl=24;
const int baza=8;
int N,step[10],potrebno[maxn];
ll dobija[maxn];
int koji[maxn][baza+1][maxl+1],suma[maxn][baza+1][maxl+1],gubit[maxn][baza+1][maxl+1];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 235 ms 143784 KB Output is correct
5 Correct 4 ms 14936 KB Output is correct
6 Correct 200 ms 143640 KB Output is correct

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3459 ms 1087828 KB Output is correct
3 Correct 3200 ms 1088384 KB Output is correct
4 Incorrect 3170 ms 1089928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12896 KB Output is correct
2 Correct 229 ms 145048 KB Output is correct
3 Correct 188 ms 145476 KB Output is correct
4 Correct 173 ms 144464 KB Output is correct
5 Correct 202 ms 144520 KB Output is correct
6 Correct 221 ms 144776 KB Output is correct
7 Correct 248 ms 144776 KB Output is correct
8 Correct 183 ms 144528 KB Output is correct
9 Correct 184 ms 144396 KB Output is correct
10 Correct 176 ms 144204 KB Output is correct
11 Correct 377 ms 144676 KB Output is correct
12 Correct 671 ms 144776 KB Output is correct
13 Correct 471 ms 144784 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12896 KB Output is correct
2 Correct 229 ms 145048 KB Output is correct
3 Correct 188 ms 145476 KB Output is correct
4 Correct 173 ms 144464 KB Output is correct
5 Correct 202 ms 144520 KB Output is correct
6 Correct 221 ms 144776 KB Output is correct
7 Correct 248 ms 144776 KB Output is correct
8 Correct 183 ms 144528 KB Output is correct
9 Correct 184 ms 144396 KB Output is correct
10 Correct 176 ms 144204 KB Output is correct
11 Correct 377 ms 144676 KB Output is correct
12 Correct 671 ms 144776 KB Output is correct
13 Correct 471 ms 144784 KB Output is correct
14 Correct 3 ms 12896 KB Output is correct
15 Correct 202 ms 144968 KB Output is correct
16 Correct 231 ms 144984 KB Output is correct
17 Correct 182 ms 144520 KB Output is correct
18 Correct 184 ms 144544 KB Output is correct
19 Correct 243 ms 144776 KB Output is correct
20 Correct 200 ms 144396 KB Output is correct
21 Correct 190 ms 144652 KB Output is correct
22 Correct 228 ms 144720 KB Output is correct
23 Correct 356 ms 144788 KB Output is correct
24 Correct 393 ms 144976 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12896 KB Output is correct
2 Correct 229 ms 145048 KB Output is correct
3 Correct 188 ms 145476 KB Output is correct
4 Correct 173 ms 144464 KB Output is correct
5 Correct 202 ms 144520 KB Output is correct
6 Correct 221 ms 144776 KB Output is correct
7 Correct 248 ms 144776 KB Output is correct
8 Correct 183 ms 144528 KB Output is correct
9 Correct 184 ms 144396 KB Output is correct
10 Correct 176 ms 144204 KB Output is correct
11 Correct 377 ms 144676 KB Output is correct
12 Correct 671 ms 144776 KB Output is correct
13 Correct 471 ms 144784 KB Output is correct
14 Correct 3 ms 12896 KB Output is correct
15 Correct 202 ms 144968 KB Output is correct
16 Correct 231 ms 144984 KB Output is correct
17 Correct 182 ms 144520 KB Output is correct
18 Correct 184 ms 144544 KB Output is correct
19 Correct 243 ms 144776 KB Output is correct
20 Correct 200 ms 144396 KB Output is correct
21 Correct 190 ms 144652 KB Output is correct
22 Correct 228 ms 144720 KB Output is correct
23 Correct 356 ms 144788 KB Output is correct
24 Correct 393 ms 144976 KB Output is correct
25 Correct 217 ms 144100 KB Output is correct
26 Correct 230 ms 145232 KB Output is correct
27 Correct 189 ms 144468 KB Output is correct
28 Correct 197 ms 144576 KB Output is correct
29 Correct 245 ms 145184 KB Output is correct
30 Correct 213 ms 144596 KB Output is correct
31 Correct 219 ms 144464 KB Output is correct
32 Correct 419 ms 144464 KB Output is correct
33 Correct 282 ms 144736 KB Output is correct
34 Correct 536 ms 144600 KB Output is correct
35 Correct 409 ms 144480 KB Output is correct

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3459 ms 1087828 KB Output is correct
3 Correct 3200 ms 1088384 KB Output is correct
4 Incorrect 3170 ms 1089928 KB Output isn't correct
5 Halted 0 ms 0 KB -