oj.uz

답안 #961553

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961553 2024-04-12T08:00:11 Z Warinchai 던전 (IOI21_dungeons) C++17
13 / 100
 918 ms 754756 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
int lift[40][40][50005];
int mn[40][40][50005];
long long dis[40][40][50005];
long long inf=1e18+7;
int N;
vector<int>W;
vector<int>S;
vector<int>L;
vector<int>P;
int X=0;
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l) {
    N=n;
    S=s;
    W=w;
    L=l;
    P=p;
    //cerr<<"work\n";
    for(int i=0;i<=25;i++){
        int st=(1<<(i-1))+1;
        int en=(1<<i);
        for(int j=0;j<n;j++){
            if(s[j]>en)lift[i][0][j]=l[j],mn[i][0][j]=inf,dis[i][0][j]=p[j];
            else if(s[j]>=st)lift[i][0][j]=l[j],mn[i][0][j]=s[j],dis[i][0][j]=p[j];
            else lift[i][0][j]=w[j],mn[i][0][j]=inf,dis[i][0][j]=s[j];
        }
        lift[i][0][n]=n;
        mn[i][0][n]=0;
        for(int j=1;j<=25;j++){
            for(int k=0;k<=n;k++){
                //cerr<<i<<" "<<j<<" "<<k<<"\n";
                lift[i][j][k]=lift[i][j-1][lift[i][j-1][k]];
                dis[i][j][k]=dis[i][j-1][k]+dis[i][j-1][lift[i][j-1][k]];
                X=mn[i][j-1][lift[i][j-1][k]]-dis[i][j-1][k];
                if(dis[i][j-1][k]>mn[i][j-1][lift[i][j-1][k]])mn[i][j][k]=0;
                else mn[i][j][k]=min(mn[i][j-1][k],X);
            }
        }
    }
    //cerr<<"work\n";
	return;
}
 
long long simulate(int x, int z) {
    //cerr<<"work\n";
    long long c=0,lv=0;
    long long pow=z;
    while(x>(1<<c)){
        lv=c;
        c++;
    }
    //cerr<<x<<"\n";
    //cerr<<lv<<"\n";
    while(1){
        //cerr<<x<<" "<<pow<<"\n";
        if(lv==25)return pow+dis[lv][25][x];
        for(int i=25;i>=0;i--){
            //cerr<<i<<" "<<lv<<" "<<x<<"\n";
            if(pow<mn[lv][i][x]&&pow+dis[lv][i][x]<=(1<<lv))pow+=dis[lv][i][x],x=lift[lv][i][x];
        }
        //cerr<<x<<" "<<pow<<"\n\n";
        if(x==N)break;
        if(pow>=S[x])pow+=S[x],x=W[x];
        else {
            pow+=P[x];
            x=L[x];
        }
        lv++;
    }
	return pow;
}

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 408144 KB Output is correct
2 Correct 44 ms 408148 KB Output is correct
3 Correct 50 ms 416708 KB Output is correct
4 Correct 216 ms 628764 KB Output is correct
5 Incorrect 52 ms 428624 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 424508 KB Output is correct
2 Incorrect 918 ms 754756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 426520 KB Output is correct
2 Correct 308 ms 629756 KB Output is correct
3 Correct 421 ms 631468 KB Output is correct
4 Correct 416 ms 630728 KB Output is correct
5 Correct 396 ms 630672 KB Output is correct
6 Correct 440 ms 630864 KB Output is correct
7 Correct 452 ms 630872 KB Output is correct
8 Correct 409 ms 630612 KB Output is correct
9 Correct 307 ms 630612 KB Output is correct
10 Correct 393 ms 630628 KB Output is correct
11 Correct 472 ms 630872 KB Output is correct
12 Correct 569 ms 631000 KB Output is correct
13 Correct 586 ms 633420 KB Output is correct

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 426520 KB Output is correct
2 Correct 308 ms 629756 KB Output is correct
3 Correct 421 ms 631468 KB Output is correct
4 Correct 416 ms 630728 KB Output is correct
5 Correct 396 ms 630672 KB Output is correct
6 Correct 440 ms 630864 KB Output is correct
7 Correct 452 ms 630872 KB Output is correct
8 Correct 409 ms 630612 KB Output is correct
9 Correct 307 ms 630612 KB Output is correct
10 Correct 393 ms 630628 KB Output is correct
11 Correct 472 ms 630872 KB Output is correct
12 Correct 569 ms 631000 KB Output is correct
13 Correct 586 ms 633420 KB Output is correct
14 Incorrect 57 ms 434516 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 426520 KB Output is correct
2 Correct 308 ms 629756 KB Output is correct
3 Correct 421 ms 631468 KB Output is correct
4 Correct 416 ms 630728 KB Output is correct
5 Correct 396 ms 630672 KB Output is correct
6 Correct 440 ms 630864 KB Output is correct
7 Correct 452 ms 630872 KB Output is correct
8 Correct 409 ms 630612 KB Output is correct
9 Correct 307 ms 630612 KB Output is correct
10 Correct 393 ms 630628 KB Output is correct
11 Correct 472 ms 630872 KB Output is correct
12 Correct 569 ms 631000 KB Output is correct
13 Correct 586 ms 633420 KB Output is correct
14 Incorrect 57 ms 434516 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 424508 KB Output is correct
2 Incorrect 918 ms 754756 KB Output isn't correct
3 Halted 0 ms 0 KB -