oj.uz

Submission #966532

# Submission time Handle Problem Language Result Execution time Memory
966532 2024-04-20T03:07:43 Z 12345678 Dungeons Game (IOI21_dungeons) C++17
0 / 100
 103 ms 250844 KB 
#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

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

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]) 
        {
            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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 250764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 250760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 250844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 250844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 250844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 250760 KB Output isn't correct
2 Halted 0 ms 0 KB -