Submission #856909

#	Time	Username	Problem	Language	Result	Execution time	Memory
856909		andrei_boaca	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2865 ms	1949392 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
int s[400005],p[400005],w[400005],l[400005],cost[400005],to[25][400005];
ll n;
int dp[25][12][400005];
ll suma[25][12][400005];
int who[25][12][400005];
int baza=3;
ll smax=0;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
    n=N;
    if(n>50000)
        baza=2;
    for(int i=0;i<n;i++)
    {
        s[i]=S[i];
        smax=max(smax,s[i]*1LL);
        p[i]=P[i];
        w[i]=W[i];
        l[i]=L[i];
    }
    w[n]=n;
    for(int k=0;k<25;k++)
    {
        for(int i=0;i<n;i++)
        {
            if(s[i]<(1<<k))
            {
                to[k][i]=w[i];
                cost[i]=s[i];
            }
            else
            {
                to[k][i]=l[i];
                cost[i]=p[i];
            }
            suma[k][0][i]=cost[i];
            who[k][0][i]=to[k][i];
        }
        cost[n]=0;
        to[k][n]=n;
        who[k][0][n]=n;
        suma[k][0][n]=0;
        for(int j=1;j<=11;j++)
        {
            for(int i=0;i<=n;i++)
            {
                ll sum=0;
                ll x=i;
                for(int c=1;c<=baza;c++)
                {
                    sum+=suma[k][j-1][x];
                    x=who[k][j-1][x];
                }
                who[k][j][i]=x;
                suma[k][j][i]=sum;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(s[i]>=(1<<k))
                dp[k][0][i]=0-s[i];
            else
                dp[k][0][i]=-1e9;
        }
        for(int j=1;j<=11;j++)
        {
            for(int i=0;i<=n;i++)
            {
                ll x=i;
                ll maxim=-1e9;
                ll sum=0;
                for(int c=1;c<=baza;c++)
                {
                    ll val=-1e9;
                    if(dp[k][j-1][x]>-1e9)
                        val=min(0LL,dp[k][j-1][x]+sum);
                    maxim=max(maxim,val);
                    sum+=suma[k][j-1][x];
                    x=who[k][j-1][x];
                }
                dp[k][j][i]=maxim;
            }
        }
    }
}

long long simulate(int x, int z)
{
    ll rez=z;
    int cnt=0;
    while(x!=n)
    {
        cnt++;
        ll k=0;
        for(int i=0;i<25;i++)
            if((1<<i)<rez)
                k=i;
        if(k==24)
        {
            while(x!=n)
            {
                rez+=suma[k][11][x];
                x=who[k][11][x];
            }
            continue;
        }
        for(int i=11;i>=0;i--)
        {
            while(rez+dp[k][i][x]<0)
            {
                rez+=suma[k][i][x];
                x=who[k][i][x];
            }
        }
        rez+=s[x];
        //assert(x==n||s[x]>=(1<<k));
        x=w[x];
    }
    return rez;
}

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