제출 #950650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
950650		12345678	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	41 ms	232148 KiB

dungeons

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

using namespace std;

#define ll long long

const int nx=4e5+5, kx=24;

struct node
{
    ll loc, sm, mx;
    node(): loc(0), sm(0), mx(0){}
    node(ll loc, ll sm, ll mx): loc(loc), sm(sm), mx(mx){}
    friend node operator+(const node &a, const node &b)
    {
        return node(b.loc, a.sm+b.sm, max(a.mx, b.mx-a.sm));
    }
} dp[nx][kx];

ll N;
vector<ll> S(nx), L(nx);

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
    for (int i=0; i<n; i++) S[i]=s[i], L[i]=l[i];
    L[n]=n;
    N=n;
    //S[n]=LLONG_MAX;
    for (int i=0; i<n; i++) dp[i][0]=node(w[i], s[i], s[w[i]]-s[i]);
    dp[n][0]=node(n, 0, -1e18);
    for (int i=1; i<kx; i++) for (int j=0; j<=n; j++) dp[j][i]=dp[j][i-1]+dp[dp[j][i-1].loc][i-1];
    //for (int i=0; i<4; i++) for (int j=0; j<=n; j++) cout<<i<<' '<<j<<' '<<dp[j][i].loc<<' '<<dp[j][i].sm<<' '<<dp[j][i].mx<<'\n';
}

long long simulate(int x, int z) {
    ll pw=z;
    while (x!=N)
    {
        //cout<<"simulate "<<i<<' '<<x<<' '<<pw<<'\n';
        if (pw<S[x]||x==N) 
        {
            pw+=S[x], x=L[x];
            continue;
        }
        for (int j=kx-1; j>=0; j--) if (pw>=dp[x][j].mx) pw+=dp[x][j].sm, x=dp[x][j].loc;
        pw+=S[x];
        x=L[x];
    }
    return pw;
}

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