oj.uz

Submission #981429

# Submission time Handle Problem Language Result Execution time Memory
981429 2024-05-13T08:00:39 Z 12345678 Dungeons Game (IOI21_dungeons) C++17
24 / 100
 1044 ms 1265968 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=5e4+5, kx=25;

ll N, pw[30];
vector<ll> S(nx), P(nx), W(nx), L(nx);

struct edge
{
    ll out, cost, t;
    edge(ll out=0, ll cost=0, ll t=0): out(out), cost(cost), t(t){}
} dp[kx][nx][kx];

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
    N=n;
    pw[0]=1;
    for (int i=1; i<30; i++) pw[i]=pw[i-1]*2;
    for (int i=0; i<n; i++) S[i]=s[i], P[i]=p[i], W[i]=w[i], L[i]=l[i];
    W[n]=L[n]=n;
    for (int i=0; i<kx; i++)
    {
        for (int u=0; u<=n; u++)
        {
            if (s[u]<=pw[i]) dp[i][u][0]=edge(W[u], S[u], 1e18);
            else dp[i][u][0]=edge(L[u], P[u], S[u]);
        }
        for (int j=1; j<kx; j++)
        {
            for (int u=0; u<=n; u++)
            {
                int v=dp[i][u][j-1].out;
                ll out=dp[i][v][j-1].out;
                ll cost=dp[i][u][j-1].cost+dp[i][v][j-1].cost;
                ll t=min(dp[i][u][j-1].t, dp[i][v][j-1].t-dp[i][u][j-1].cost);
                dp[i][u][j]=edge(out, cost, t);
            }
        }
    }
}

long long simulate(int x, int z) {
    ll cur=z, st=0;
    while (x!=N)
    {
        //cout<<"debug "<<x<<' '<<cur<<' '<<st<<'\n';
        while (pw[st+1]<=cur) st++;
        for (int i=kx-1; i>=0; i--) if (dp[st][x][i].t>cur) cur+=dp[st][x][i].cost, x=dp[st][x][i].out; //cout<<"here "<<i<<' '<<cur<<' '<<x<<'\n';
        //cout<<"after "<<x<<' '<<cur<<' '<<st<<'\n';
        if (cur>=S[x]) cur+=S[x], x=W[x];
        else cur+=P[x], x=L[x];
    }
	return cur;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 735812 KB Output is correct
2 Correct 197 ms 735684 KB Output is correct
3 Correct 208 ms 735824 KB Output is correct
4 Correct 469 ms 737636 KB Output is correct
5 Correct 206 ms 735984 KB Output is correct
6 Correct 435 ms 737688 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 616 ms 1263072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 735784 KB Output is correct
2 Correct 478 ms 738496 KB Output is correct
3 Correct 468 ms 738516 KB Output is correct
4 Correct 455 ms 739396 KB Output is correct
5 Correct 461 ms 739280 KB Output is correct
6 Correct 473 ms 739412 KB Output is correct
7 Correct 492 ms 739636 KB Output is correct
8 Correct 509 ms 739280 KB Output is correct
9 Correct 445 ms 739136 KB Output is correct
10 Correct 465 ms 739388 KB Output is correct
11 Correct 571 ms 739464 KB Output is correct
12 Correct 619 ms 739440 KB Output is correct
13 Correct 571 ms 739532 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 735784 KB Output is correct
2 Correct 478 ms 738496 KB Output is correct
3 Correct 468 ms 738516 KB Output is correct
4 Correct 455 ms 739396 KB Output is correct
5 Correct 461 ms 739280 KB Output is correct
6 Correct 473 ms 739412 KB Output is correct
7 Correct 492 ms 739636 KB Output is correct
8 Correct 509 ms 739280 KB Output is correct
9 Correct 445 ms 739136 KB Output is correct
10 Correct 465 ms 739388 KB Output is correct
11 Correct 571 ms 739464 KB Output is correct
12 Correct 619 ms 739440 KB Output is correct
13 Correct 571 ms 739532 KB Output is correct
14 Correct 205 ms 735936 KB Output is correct
15 Correct 474 ms 739668 KB Output is correct
16 Runtime error 1044 ms 1265968 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 735784 KB Output is correct
2 Correct 478 ms 738496 KB Output is correct
3 Correct 468 ms 738516 KB Output is correct
4 Correct 455 ms 739396 KB Output is correct
5 Correct 461 ms 739280 KB Output is correct
6 Correct 473 ms 739412 KB Output is correct
7 Correct 492 ms 739636 KB Output is correct
8 Correct 509 ms 739280 KB Output is correct
9 Correct 445 ms 739136 KB Output is correct
10 Correct 465 ms 739388 KB Output is correct
11 Correct 571 ms 739464 KB Output is correct
12 Correct 619 ms 739440 KB Output is correct
13 Correct 571 ms 739532 KB Output is correct
14 Correct 205 ms 735936 KB Output is correct
15 Correct 474 ms 739668 KB Output is correct
16 Runtime error 1044 ms 1265968 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 616 ms 1263072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -