oj.uz

Submission #856900

# Submission time Handle Problem Language Result Execution time Memory
856900 2023-10-04T19:35:03 Z andrei_boaca Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1945692 KB 
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
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][400005][12];
ll suma[25][400005][12];
int who[25][400005][12];
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<=11;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][11];
                x=who[k][x][11];
            }
            continue;
        }
        for(int i=8;i>=0;i--)
        {
            while(rez+dp[k][x][i]<0)
            {
                rez+=suma[k][x][i];
                x=who[k][x][i];
            }
        }
        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 18 ms 199260 KB Output is correct
2 Correct 19 ms 199420 KB Output is correct
3 Correct 28 ms 207696 KB Output is correct
4 Correct 353 ms 435064 KB Output is correct
5 Correct 29 ms 207700 KB Output is correct
6 Correct 330 ms 435024 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 203612 KB Output is correct
2 Correct 4057 ms 1939404 KB Output is correct
3 Correct 3768 ms 1941544 KB Output is correct
4 Correct 3981 ms 1943612 KB Output is correct
5 Correct 5477 ms 1945692 KB Output is correct
6 Correct 3734 ms 1944856 KB Output is correct
7 Correct 3346 ms 1943868 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 203612 KB Output is correct
2 Correct 400 ms 437584 KB Output is correct
3 Correct 319 ms 437332 KB Output is correct
4 Correct 294 ms 435736 KB Output is correct
5 Correct 305 ms 435736 KB Output is correct
6 Correct 377 ms 435796 KB Output is correct
7 Correct 415 ms 435872 KB Output is correct
8 Correct 308 ms 435792 KB Output is correct
9 Correct 356 ms 435816 KB Output is correct
10 Correct 315 ms 435772 KB Output is correct
11 Correct 507 ms 436128 KB Output is correct
12 Correct 1085 ms 435772 KB Output is correct
13 Correct 868 ms 435908 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 203612 KB Output is correct
2 Correct 400 ms 437584 KB Output is correct
3 Correct 319 ms 437332 KB Output is correct
4 Correct 294 ms 435736 KB Output is correct
5 Correct 305 ms 435736 KB Output is correct
6 Correct 377 ms 435796 KB Output is correct
7 Correct 415 ms 435872 KB Output is correct
8 Correct 308 ms 435792 KB Output is correct
9 Correct 356 ms 435816 KB Output is correct
10 Correct 315 ms 435772 KB Output is correct
11 Correct 507 ms 436128 KB Output is correct
12 Correct 1085 ms 435772 KB Output is correct
13 Correct 868 ms 435908 KB Output is correct
14 Correct 24 ms 203608 KB Output is correct
15 Correct 340 ms 435676 KB Output is correct
16 Correct 405 ms 436052 KB Output is correct
17 Correct 317 ms 435932 KB Output is correct
18 Correct 320 ms 435796 KB Output is correct
19 Correct 409 ms 435684 KB Output is correct
20 Correct 324 ms 436052 KB Output is correct
21 Correct 321 ms 435708 KB Output is correct
22 Correct 341 ms 436052 KB Output is correct
23 Correct 471 ms 435932 KB Output is correct
24 Correct 656 ms 436060 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 203612 KB Output is correct
2 Correct 400 ms 437584 KB Output is correct
3 Correct 319 ms 437332 KB Output is correct
4 Correct 294 ms 435736 KB Output is correct
5 Correct 305 ms 435736 KB Output is correct
6 Correct 377 ms 435796 KB Output is correct
7 Correct 415 ms 435872 KB Output is correct
8 Correct 308 ms 435792 KB Output is correct
9 Correct 356 ms 435816 KB Output is correct
10 Correct 315 ms 435772 KB Output is correct
11 Correct 507 ms 436128 KB Output is correct
12 Correct 1085 ms 435772 KB Output is correct
13 Correct 868 ms 435908 KB Output is correct
14 Correct 24 ms 203608 KB Output is correct
15 Correct 340 ms 435676 KB Output is correct
16 Correct 405 ms 436052 KB Output is correct
17 Correct 317 ms 435932 KB Output is correct
18 Correct 320 ms 435796 KB Output is correct
19 Correct 409 ms 435684 KB Output is correct
20 Correct 324 ms 436052 KB Output is correct
21 Correct 321 ms 435708 KB Output is correct
22 Correct 341 ms 436052 KB Output is correct
23 Correct 471 ms 435932 KB Output is correct
24 Correct 656 ms 436060 KB Output is correct
25 Correct 359 ms 435288 KB Output is correct
26 Correct 377 ms 435708 KB Output is correct
27 Correct 334 ms 436052 KB Output is correct
28 Correct 326 ms 435684 KB Output is correct
29 Correct 398 ms 436048 KB Output is correct
30 Correct 345 ms 435792 KB Output is correct
31 Correct 342 ms 436216 KB Output is correct
32 Correct 590 ms 435792 KB Output is correct
33 Correct 373 ms 435792 KB Output is correct
34 Correct 559 ms 435956 KB Output is correct
35 Correct 469 ms 435932 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 203612 KB Output is correct
2 Correct 4057 ms 1939404 KB Output is correct
3 Correct 3768 ms 1941544 KB Output is correct
4 Correct 3981 ms 1943612 KB Output is correct
5 Correct 5477 ms 1945692 KB Output is correct
6 Correct 3734 ms 1944856 KB Output is correct
7 Correct 3346 ms 1943868 KB Output is correct
8 Correct 24 ms 203612 KB Output is correct
9 Correct 400 ms 437584 KB Output is correct
10 Correct 319 ms 437332 KB Output is correct
11 Correct 294 ms 435736 KB Output is correct
12 Correct 305 ms 435736 KB Output is correct
13 Correct 377 ms 435796 KB Output is correct
14 Correct 415 ms 435872 KB Output is correct
15 Correct 308 ms 435792 KB Output is correct
16 Correct 356 ms 435816 KB Output is correct
17 Correct 315 ms 435772 KB Output is correct
18 Correct 507 ms 436128 KB Output is correct
19 Correct 1085 ms 435772 KB Output is correct
20 Correct 868 ms 435908 KB Output is correct
21 Correct 24 ms 203608 KB Output is correct
22 Correct 340 ms 435676 KB Output is correct
23 Correct 405 ms 436052 KB Output is correct
24 Correct 317 ms 435932 KB Output is correct
25 Correct 320 ms 435796 KB Output is correct
26 Correct 409 ms 435684 KB Output is correct
27 Correct 324 ms 436052 KB Output is correct
28 Correct 321 ms 435708 KB Output is correct
29 Correct 341 ms 436052 KB Output is correct
30 Correct 471 ms 435932 KB Output is correct
31 Correct 656 ms 436060 KB Output is correct
32 Correct 359 ms 435288 KB Output is correct
33 Correct 377 ms 435708 KB Output is correct
34 Correct 334 ms 436052 KB Output is correct
35 Correct 326 ms 435684 KB Output is correct
36 Correct 398 ms 436048 KB Output is correct
37 Correct 345 ms 435792 KB Output is correct
38 Correct 342 ms 436216 KB Output is correct
39 Correct 590 ms 435792 KB Output is correct
40 Correct 373 ms 435792 KB Output is correct
41 Correct 559 ms 435956 KB Output is correct
42 Correct 469 ms 435932 KB Output is correct
43 Correct 19 ms 199516 KB Output is correct
44 Correct 23 ms 203608 KB Output is correct
45 Execution timed out 7035 ms 1710836 KB Time limit exceeded
46 Halted 0 ms 0 KB -