제출 #712757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
712757		danikoynov	던전 (IOI21_dungeons)	C++17	100 / 100	4343 ms	1913628 KiB

dungeons

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

using namespace std;
typedef long long ll;

const int maxn = 4e5 + 10, maxlog = 14;

int n, w[maxn], l[maxn];
ll s[maxn], p[maxn];

vector < int > child[maxn];

struct jump
{
    ll sum, best;
    int ver;
};


jump dp[maxlog][maxlog][maxn];

bool all_same = true;
set < ll > st;
vector < ll > values;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
    n = N;
    for (int i = 0; i < n; i ++)
    {
        s[i] = S[i];
        p[i] = P[i];
        w[i] = W[i];
        l[i] = L[i];
        st.insert(s[i]);

        child[w[i]].push_back(i);
    }
    for (auto it : st)
        values.push_back(it);

    for (int i = 1; i < n; i ++)
    {
        if (s[i] != s[i - 1])
            all_same = false;
    }


    w[n] = n;
    l[n] = n;


    for (int k = 0; k < maxlog; k ++)
    {
        for (int i = 0; i <= n; i ++)
        {
            if (s[i] >= (1 << (k * 2)))
            {
                dp[k][0][i].ver = l[i];
                dp[k][0][i].best = - s[i];
                dp[k][0][i].sum = p[i];
            }
            else
            {
                dp[k][0][i].ver = w[i];
                dp[k][0][i].best = -1e18;
                dp[k][0][i].sum = s[i];
            }

        }

        for (int j = 1; j < maxlog; j ++)
            for (int i = 0; i <= n; i ++)
            {
                dp[k][j][i].ver = dp[k][j - 1][i].ver;
                dp[k][j][i].sum = dp[k][j - 1][i].sum;
                dp[k][j][i].best = dp[k][j - 1][i].best;
                for (int p = 0; p < 3; p ++)
                {


                    dp[k][j][i].best = max(dp[k][j][i].best, dp[k][j - 1][dp[k][j][i].ver].best + dp[k][j][i].sum);
                    dp[k][j][i].sum = dp[k][j - 1][dp[k][j][i].ver].sum + dp[k][j][i].sum;
                    dp[k][j][i].ver = dp[k][j - 1][dp[k][j][i].ver].ver;
                }
                ///if (j == 1)
                ///cout << k << " " << j << " " << i << " " << dp[k][j][i].best << endl;
            }
    }


    return;
}

long long simulate(int x, int z)
{
    ll strength = z;
    while(x != n)
    {

        int bit = maxlog - 1;
        while(strength < (1 << (bit * 2)))
            bit --;
            ///cout << x << " " << strength << " " << bit << endl;
        ///cout << x << " :: " << strength << " " << bit << endl;
        for (int j = maxlog - 1; j >= 0; j --)
        {
            for (int p = 0; p < 3; p ++)
            if (strength + dp[bit][j][x].best < 0)
            {
                ///cout << j << " --- " << dp[bit][j][x].ver << endl;
                strength = strength + dp[bit][j][x].sum;
                x = dp[bit][j][x].ver;
            }
            ///else cout << strength << " :::: "  << dp[bit][j][x].best << endl;
        }
        strength = strength + s[x];
        x = w[x];

    }
    return strength;
}

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