oj.uz

Submission #856890

# Submission time Handle Problem Language Result Execution time Memory
856890 2023-10-04T19:13:18 Z andrei_boaca Dungeons Game (IOI21_dungeons) C++17
63 / 100
 7000 ms 349260 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][50005][12];
ll suma[25][50005][12];
int who[25][50005][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<12;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<12;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);
                    assert(maxim<=0);
                    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=11;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 20 ms 213648 KB Output is correct
2 Correct 20 ms 213596 KB Output is correct
3 Correct 34 ms 220112 KB Output is correct
4 Correct 335 ms 312032 KB Output is correct
5 Correct 29 ms 219924 KB Output is correct
6 Correct 331 ms 312020 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 219988 KB Output is correct
2 Execution timed out 7028 ms 349260 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 219988 KB Output is correct
2 Correct 449 ms 312804 KB Output is correct
3 Correct 332 ms 312660 KB Output is correct
4 Correct 311 ms 312776 KB Output is correct
5 Correct 288 ms 312568 KB Output is correct
6 Correct 387 ms 312744 KB Output is correct
7 Correct 361 ms 312564 KB Output is correct
8 Correct 320 ms 312964 KB Output is correct
9 Correct 317 ms 312912 KB Output is correct
10 Correct 305 ms 312856 KB Output is correct
11 Correct 491 ms 312680 KB Output is correct
12 Correct 635 ms 312824 KB Output is correct
13 Correct 361 ms 314008 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 219988 KB Output is correct
2 Correct 449 ms 312804 KB Output is correct
3 Correct 332 ms 312660 KB Output is correct
4 Correct 311 ms 312776 KB Output is correct
5 Correct 288 ms 312568 KB Output is correct
6 Correct 387 ms 312744 KB Output is correct
7 Correct 361 ms 312564 KB Output is correct
8 Correct 320 ms 312964 KB Output is correct
9 Correct 317 ms 312912 KB Output is correct
10 Correct 305 ms 312856 KB Output is correct
11 Correct 491 ms 312680 KB Output is correct
12 Correct 635 ms 312824 KB Output is correct
13 Correct 361 ms 314008 KB Output is correct
14 Correct 25 ms 219992 KB Output is correct
15 Correct 334 ms 314272 KB Output is correct
16 Correct 422 ms 314240 KB Output is correct
17 Correct 303 ms 313924 KB Output is correct
18 Correct 325 ms 313808 KB Output is correct
19 Correct 415 ms 314040 KB Output is correct
20 Correct 333 ms 313672 KB Output is correct
21 Correct 316 ms 313936 KB Output is correct
22 Correct 330 ms 313824 KB Output is correct
23 Correct 472 ms 314196 KB Output is correct
24 Correct 680 ms 313944 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 219988 KB Output is correct
2 Correct 449 ms 312804 KB Output is correct
3 Correct 332 ms 312660 KB Output is correct
4 Correct 311 ms 312776 KB Output is correct
5 Correct 288 ms 312568 KB Output is correct
6 Correct 387 ms 312744 KB Output is correct
7 Correct 361 ms 312564 KB Output is correct
8 Correct 320 ms 312964 KB Output is correct
9 Correct 317 ms 312912 KB Output is correct
10 Correct 305 ms 312856 KB Output is correct
11 Correct 491 ms 312680 KB Output is correct
12 Correct 635 ms 312824 KB Output is correct
13 Correct 361 ms 314008 KB Output is correct
14 Correct 25 ms 219992 KB Output is correct
15 Correct 334 ms 314272 KB Output is correct
16 Correct 422 ms 314240 KB Output is correct
17 Correct 303 ms 313924 KB Output is correct
18 Correct 325 ms 313808 KB Output is correct
19 Correct 415 ms 314040 KB Output is correct
20 Correct 333 ms 313672 KB Output is correct
21 Correct 316 ms 313936 KB Output is correct
22 Correct 330 ms 313824 KB Output is correct
23 Correct 472 ms 314196 KB Output is correct
24 Correct 680 ms 313944 KB Output is correct
25 Correct 364 ms 313384 KB Output is correct
26 Correct 395 ms 314324 KB Output is correct
27 Correct 348 ms 313808 KB Output is correct
28 Correct 342 ms 313924 KB Output is correct
29 Correct 411 ms 314196 KB Output is correct
30 Correct 341 ms 314308 KB Output is correct
31 Correct 331 ms 313680 KB Output is correct
32 Correct 592 ms 314084 KB Output is correct
33 Correct 385 ms 314044 KB Output is correct
34 Correct 602 ms 313832 KB Output is correct
35 Correct 511 ms 313704 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 219988 KB Output is correct
2 Execution timed out 7028 ms 349260 KB Time limit exceeded
3 Halted 0 ms 0 KB -