제출 #1068080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1068080		RaresFelix	던전 (IOI21_dungeons)	C++17	37 / 100	7057 ms	1165060 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;

const int B = 5;
const int C = 5;
const int MPB = 11;
const int MK = 11;
const int MN = 400000;

const int MV = 1e7;
const int INF = 1e9;

struct salt {
    int u; // in ce nod am ajuns
    ll delta, smax;

    salt operator+(const salt &rhs) {
        salt re; /// prima data fac eu, dupa rhs
        re.smax = min(smax, rhs.smax - delta);
        re.delta = rhs.delta + delta;
        re.u = rhs.u;
        return re;
    }
};

salt DP[MN][MPB][MK];
int n;
vi s, delta_l, w, l;

void init(int n0, vi s0, vi delta_l0, vi w0, vi l0) {
    n = n0;
    s = s0; delta_l = delta_l0; w = w0; l = l0;
    int pow = 1;
    for(int p = 0; p < MPB; ++p) {
        ///pow... pow * B - 1
        for(int i = 0; i < n; ++i) {
            if(s[i] <= pow) {
                DP[i][p][0] = salt{w[i], s[i], INF};
            } else {
                DP[i][p][0] = salt{l[i], delta_l[i], s[i] - 1};
            }
        }
        for(int k = 1; k < MK; ++k) {
            /// C ^ k e saltul
            for(int i = 0; i < n; ++i) {
                salt eu = DP[i][p][k - 1];
                for(int j = 1; j < C; ++j) {
                    if(eu.u == n) break;
                    salt nou = DP[eu.u][p][k - 1];
                    eu = eu + nou;
                }
                DP[i][p][k] = eu;
            }
        }
        pow *= B;
    }
	return;
}

ll simulate(int x, int z) {
    int p = 0, pow = 1;
    while(x < n) {
        while(pow * B <= min(z, MV)) {
            ++p; pow *= B;
        }
        p = min(p, MPB - 1);
        for(int k = MK - 1; k >= 0; --k) {
            while(x < n) {
                salt eu = DP[x][p][k];
                if(eu.smax < z) break;
                x = eu.u;
                z += eu.delta;
            }
            if(x == n) break;
        }
        if(x == n) break;
        if(z >= s[x]) {
            z += s[x];
            x = w[x];
        } else {
            z += delta_l[x];
            x = l[x];
        }
    }
	return z;
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11