oj.uz

답안 #961558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961558 2024-04-12T08:04:42 Z Warinchai 던전 (IOI21_dungeons) C++17
13 / 100
 2335 ms 1770936 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
int lift[50][50][50005];
int mn[50][50][50005];
long long dis[50][50][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<=45;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<=40;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][40][x];
        for(int i=40;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 55 ms 478984 KB Output is correct
2 Correct 56 ms 483156 KB Output is correct
3 Correct 77 ms 524112 KB Output is correct
4 Correct 833 ms 1547984 KB Output is correct
5 Incorrect 79 ms 528076 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 504664 KB Output is correct
2 Incorrect 2335 ms 1770936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 528592 KB Output is correct
2 Correct 887 ms 1555216 KB Output is correct
3 Correct 1164 ms 1557936 KB Output is correct
4 Correct 1070 ms 1562096 KB Output is correct
5 Correct 1052 ms 1562240 KB Output is correct
6 Correct 991 ms 1562128 KB Output is correct
7 Correct 1050 ms 1562136 KB Output is correct
8 Correct 920 ms 1561812 KB Output is correct
9 Correct 738 ms 1561972 KB Output is correct
10 Correct 893 ms 1561764 KB Output is correct
11 Correct 960 ms 1562292 KB Output is correct
12 Correct 1185 ms 1562256 KB Output is correct
13 Correct 989 ms 1561344 KB Output is correct

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 528592 KB Output is correct
2 Correct 887 ms 1555216 KB Output is correct
3 Correct 1164 ms 1557936 KB Output is correct
4 Correct 1070 ms 1562096 KB Output is correct
5 Correct 1052 ms 1562240 KB Output is correct
6 Correct 991 ms 1562128 KB Output is correct
7 Correct 1050 ms 1562136 KB Output is correct
8 Correct 920 ms 1561812 KB Output is correct
9 Correct 738 ms 1561972 KB Output is correct
10 Correct 893 ms 1561764 KB Output is correct
11 Correct 960 ms 1562292 KB Output is correct
12 Correct 1185 ms 1562256 KB Output is correct
13 Correct 989 ms 1561344 KB Output is correct
14 Incorrect 78 ms 568108 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 528592 KB Output is correct
2 Correct 887 ms 1555216 KB Output is correct
3 Correct 1164 ms 1557936 KB Output is correct
4 Correct 1070 ms 1562096 KB Output is correct
5 Correct 1052 ms 1562240 KB Output is correct
6 Correct 991 ms 1562128 KB Output is correct
7 Correct 1050 ms 1562136 KB Output is correct
8 Correct 920 ms 1561812 KB Output is correct
9 Correct 738 ms 1561972 KB Output is correct
10 Correct 893 ms 1561764 KB Output is correct
11 Correct 960 ms 1562292 KB Output is correct
12 Correct 1185 ms 1562256 KB Output is correct
13 Correct 989 ms 1561344 KB Output is correct
14 Incorrect 78 ms 568108 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 504664 KB Output is correct
2 Incorrect 2335 ms 1770936 KB Output isn't correct
3 Halted 0 ms 0 KB -