oj.uz

Submission #856897

# Submission time Handle Problem Language Result Execution time Memory
856897 2023-10-04T19:28:53 Z andrei_boaca Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1876620 KB 
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
ll s[400005],p[400005],w[400005],l[400005],cost[400005],to[25][400005];
ll n;
int dp[25][400005][12];
ll suma[25][400005][11];
int who[25][400005][11];
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;
    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][i][0]=cost[i];
            who[k][i][0]=to[k][i];
        }
        cost[n]=0;
        to[k][n]=n;
        who[k][n][0]=n;
        suma[k][n][0]=0;
        for(int j=1;j<=10;j++)
        {
            for(int i=0;i<=n;i++)
            {
                ll sum=0;
                ll x=i;
                for(int c=1;c<=4;c++)
                {
                    sum+=suma[k][x][j-1];
                    x=who[k][x][j-1];
                }
                who[k][i][j]=x;
                suma[k][i][j]=sum;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(s[i]>=(1<<k))
                dp[k][i][0]=0-s[i];
            else
                dp[k][i][0]=-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<=4;c++)
                {
                    ll val=-1e9;
                    if(dp[k][x][j-1]>-1e9)
                        val=min(0LL,dp[k][x][j-1]+sum);
                    maxim=max(maxim,val);
                    sum+=suma[k][x][j-1];
                    x=who[k][x][j-1];
                }
                dp[k][i][j]=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][x][10];
                x=who[k][x][10];
            }
            continue;
        }
        for(int i=11;i>=0;i--)
        {
            while(rez+dp[k][x][i]<0)
            {
                if(i!=11)
                {
                    rez+=suma[k][x][i];
                    x=who[k][x][i];
                }
                else
                {
                    rez+=suma[k][x][i-1];
                    x=who[k][x][i-1];
                    rez+=suma[k][x][i-1];
                    x=who[k][x][i-1];
                }
            }
        }
        rez+=s[x];
        //assert(x==n||s[x]>=(1<<k));
        x=w[x];
    }
    return rez;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 213848 KB Output is correct
2 Correct 20 ms 213852 KB Output is correct
3 Correct 32 ms 224220 KB Output is correct
4 Correct 352 ms 449332 KB Output is correct
5 Correct 31 ms 224088 KB Output is correct
6 Correct 362 ms 449488 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 218008 KB Output is correct
2 Correct 3454 ms 1869148 KB Output is correct
3 Correct 3519 ms 1875232 KB Output is correct
4 Correct 3641 ms 1875000 KB Output is correct
5 Correct 4253 ms 1876620 KB Output is correct
6 Correct 3228 ms 1874100 KB Output is correct
7 Correct 3083 ms 1873480 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 217948 KB Output is correct
2 Correct 458 ms 451916 KB Output is correct
3 Correct 361 ms 451876 KB Output is correct
4 Correct 313 ms 450268 KB Output is correct
5 Correct 311 ms 450480 KB Output is correct
6 Correct 408 ms 450124 KB Output is correct
7 Correct 421 ms 450132 KB Output is correct
8 Correct 347 ms 450156 KB Output is correct
9 Correct 370 ms 450228 KB Output is correct
10 Correct 333 ms 450536 KB Output is correct
11 Correct 520 ms 450260 KB Output is correct
12 Correct 753 ms 450268 KB Output is correct
13 Correct 411 ms 450300 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 217948 KB Output is correct
2 Correct 458 ms 451916 KB Output is correct
3 Correct 361 ms 451876 KB Output is correct
4 Correct 313 ms 450268 KB Output is correct
5 Correct 311 ms 450480 KB Output is correct
6 Correct 408 ms 450124 KB Output is correct
7 Correct 421 ms 450132 KB Output is correct
8 Correct 347 ms 450156 KB Output is correct
9 Correct 370 ms 450228 KB Output is correct
10 Correct 333 ms 450536 KB Output is correct
11 Correct 520 ms 450260 KB Output is correct
12 Correct 753 ms 450268 KB Output is correct
13 Correct 411 ms 450300 KB Output is correct
14 Correct 27 ms 217936 KB Output is correct
15 Correct 359 ms 450192 KB Output is correct
16 Correct 430 ms 450280 KB Output is correct
17 Correct 335 ms 450240 KB Output is correct
18 Correct 329 ms 450128 KB Output is correct
19 Correct 412 ms 450232 KB Output is correct
20 Correct 350 ms 450268 KB Output is correct
21 Correct 349 ms 450296 KB Output is correct
22 Correct 346 ms 450160 KB Output is correct
23 Correct 519 ms 450228 KB Output is correct
24 Correct 680 ms 450288 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 217948 KB Output is correct
2 Correct 458 ms 451916 KB Output is correct
3 Correct 361 ms 451876 KB Output is correct
4 Correct 313 ms 450268 KB Output is correct
5 Correct 311 ms 450480 KB Output is correct
6 Correct 408 ms 450124 KB Output is correct
7 Correct 421 ms 450132 KB Output is correct
8 Correct 347 ms 450156 KB Output is correct
9 Correct 370 ms 450228 KB Output is correct
10 Correct 333 ms 450536 KB Output is correct
11 Correct 520 ms 450260 KB Output is correct
12 Correct 753 ms 450268 KB Output is correct
13 Correct 411 ms 450300 KB Output is correct
14 Correct 27 ms 217936 KB Output is correct
15 Correct 359 ms 450192 KB Output is correct
16 Correct 430 ms 450280 KB Output is correct
17 Correct 335 ms 450240 KB Output is correct
18 Correct 329 ms 450128 KB Output is correct
19 Correct 412 ms 450232 KB Output is correct
20 Correct 350 ms 450268 KB Output is correct
21 Correct 349 ms 450296 KB Output is correct
22 Correct 346 ms 450160 KB Output is correct
23 Correct 519 ms 450228 KB Output is correct
24 Correct 680 ms 450288 KB Output is correct
25 Correct 400 ms 449332 KB Output is correct
26 Correct 433 ms 450348 KB Output is correct
27 Correct 401 ms 450252 KB Output is correct
28 Correct 351 ms 450084 KB Output is correct
29 Correct 434 ms 450132 KB Output is correct
30 Correct 368 ms 450100 KB Output is correct
31 Correct 349 ms 450288 KB Output is correct
32 Correct 658 ms 450160 KB Output is correct
33 Correct 418 ms 450128 KB Output is correct
34 Correct 644 ms 450588 KB Output is correct
35 Correct 514 ms 450276 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 218008 KB Output is correct
2 Correct 3454 ms 1869148 KB Output is correct
3 Correct 3519 ms 1875232 KB Output is correct
4 Correct 3641 ms 1875000 KB Output is correct
5 Correct 4253 ms 1876620 KB Output is correct
6 Correct 3228 ms 1874100 KB Output is correct
7 Correct 3083 ms 1873480 KB Output is correct
8 Correct 26 ms 217948 KB Output is correct
9 Correct 458 ms 451916 KB Output is correct
10 Correct 361 ms 451876 KB Output is correct
11 Correct 313 ms 450268 KB Output is correct
12 Correct 311 ms 450480 KB Output is correct
13 Correct 408 ms 450124 KB Output is correct
14 Correct 421 ms 450132 KB Output is correct
15 Correct 347 ms 450156 KB Output is correct
16 Correct 370 ms 450228 KB Output is correct
17 Correct 333 ms 450536 KB Output is correct
18 Correct 520 ms 450260 KB Output is correct
19 Correct 753 ms 450268 KB Output is correct
20 Correct 411 ms 450300 KB Output is correct
21 Correct 27 ms 217936 KB Output is correct
22 Correct 359 ms 450192 KB Output is correct
23 Correct 430 ms 450280 KB Output is correct
24 Correct 335 ms 450240 KB Output is correct
25 Correct 329 ms 450128 KB Output is correct
26 Correct 412 ms 450232 KB Output is correct
27 Correct 350 ms 450268 KB Output is correct
28 Correct 349 ms 450296 KB Output is correct
29 Correct 346 ms 450160 KB Output is correct
30 Correct 519 ms 450228 KB Output is correct
31 Correct 680 ms 450288 KB Output is correct
32 Correct 400 ms 449332 KB Output is correct
33 Correct 433 ms 450348 KB Output is correct
34 Correct 401 ms 450252 KB Output is correct
35 Correct 351 ms 450084 KB Output is correct
36 Correct 434 ms 450132 KB Output is correct
37 Correct 368 ms 450100 KB Output is correct
38 Correct 349 ms 450288 KB Output is correct
39 Correct 658 ms 450160 KB Output is correct
40 Correct 418 ms 450128 KB Output is correct
41 Correct 644 ms 450588 KB Output is correct
42 Correct 514 ms 450276 KB Output is correct
43 Correct 20 ms 213852 KB Output is correct
44 Correct 27 ms 217944 KB Output is correct
45 Execution timed out 7046 ms 1665200 KB Time limit exceeded
46 Halted 0 ms 0 KB -