oj.uz

Submission #981446

# Submission time Handle Problem Language Result Execution time Memory
981446 2024-05-13T08:24:56 Z 12345678 Dungeons Game (IOI21_dungeons) C++17
63 / 100
 788 ms 567120 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

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

ll N, pw[20];
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[lx][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<20; i++) pw[i]=pw[i-1]*8;
    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<lx; 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 (st+1<lx&&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 124 ms 265996 KB Output is correct
2 Correct 44 ms 266092 KB Output is correct
3 Correct 43 ms 266060 KB Output is correct
4 Correct 138 ms 268624 KB Output is correct
5 Correct 44 ms 266104 KB Output is correct
6 Correct 151 ms 268556 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 266240 KB Output is correct
2 Runtime error 407 ms 567120 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 266072 KB Output is correct
2 Correct 200 ms 269308 KB Output is correct
3 Correct 190 ms 269740 KB Output is correct
4 Correct 168 ms 269688 KB Output is correct
5 Correct 155 ms 269628 KB Output is correct
6 Correct 194 ms 269904 KB Output is correct
7 Correct 179 ms 269808 KB Output is correct
8 Correct 158 ms 269396 KB Output is correct
9 Correct 155 ms 269552 KB Output is correct
10 Correct 157 ms 269320 KB Output is correct
11 Correct 173 ms 269652 KB Output is correct
12 Correct 257 ms 270116 KB Output is correct
13 Correct 221 ms 269748 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 266072 KB Output is correct
2 Correct 200 ms 269308 KB Output is correct
3 Correct 190 ms 269740 KB Output is correct
4 Correct 168 ms 269688 KB Output is correct
5 Correct 155 ms 269628 KB Output is correct
6 Correct 194 ms 269904 KB Output is correct
7 Correct 179 ms 269808 KB Output is correct
8 Correct 158 ms 269396 KB Output is correct
9 Correct 155 ms 269552 KB Output is correct
10 Correct 157 ms 269320 KB Output is correct
11 Correct 173 ms 269652 KB Output is correct
12 Correct 257 ms 270116 KB Output is correct
13 Correct 221 ms 269748 KB Output is correct
14 Correct 42 ms 266072 KB Output is correct
15 Correct 172 ms 270176 KB Output is correct
16 Correct 184 ms 270144 KB Output is correct
17 Correct 161 ms 269708 KB Output is correct
18 Correct 175 ms 269652 KB Output is correct
19 Correct 181 ms 269680 KB Output is correct
20 Correct 177 ms 269348 KB Output is correct
21 Correct 185 ms 269664 KB Output is correct
22 Correct 174 ms 269696 KB Output is correct
23 Correct 178 ms 269828 KB Output is correct
24 Correct 270 ms 270216 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 266072 KB Output is correct
2 Correct 200 ms 269308 KB Output is correct
3 Correct 190 ms 269740 KB Output is correct
4 Correct 168 ms 269688 KB Output is correct
5 Correct 155 ms 269628 KB Output is correct
6 Correct 194 ms 269904 KB Output is correct
7 Correct 179 ms 269808 KB Output is correct
8 Correct 158 ms 269396 KB Output is correct
9 Correct 155 ms 269552 KB Output is correct
10 Correct 157 ms 269320 KB Output is correct
11 Correct 173 ms 269652 KB Output is correct
12 Correct 257 ms 270116 KB Output is correct
13 Correct 221 ms 269748 KB Output is correct
14 Correct 42 ms 266072 KB Output is correct
15 Correct 172 ms 270176 KB Output is correct
16 Correct 184 ms 270144 KB Output is correct
17 Correct 161 ms 269708 KB Output is correct
18 Correct 175 ms 269652 KB Output is correct
19 Correct 181 ms 269680 KB Output is correct
20 Correct 177 ms 269348 KB Output is correct
21 Correct 185 ms 269664 KB Output is correct
22 Correct 174 ms 269696 KB Output is correct
23 Correct 178 ms 269828 KB Output is correct
24 Correct 270 ms 270216 KB Output is correct
25 Correct 137 ms 268896 KB Output is correct
26 Correct 183 ms 270028 KB Output is correct
27 Correct 161 ms 269556 KB Output is correct
28 Correct 161 ms 269632 KB Output is correct
29 Correct 188 ms 269908 KB Output is correct
30 Correct 195 ms 269652 KB Output is correct
31 Correct 202 ms 269392 KB Output is correct
32 Correct 227 ms 269652 KB Output is correct
33 Correct 337 ms 269828 KB Output is correct
34 Correct 788 ms 269888 KB Output is correct
35 Correct 265 ms 269648 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 266240 KB Output is correct
2 Runtime error 407 ms 567120 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -