oj.uz

Submission #856909

# Submission time Handle Problem Language Result Execution time Memory
856909 2023-10-04T19:46:34 Z andrei_boaca Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2865 ms 1949392 KB 
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
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][12][400005];
ll suma[25][12][400005];
int who[25][12][400005];
int baza=3;
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;
    if(n>50000)
        baza=2;
    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][0][i]=cost[i];
            who[k][0][i]=to[k][i];
        }
        cost[n]=0;
        to[k][n]=n;
        who[k][0][n]=n;
        suma[k][0][n]=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<=baza;c++)
                {
                    sum+=suma[k][j-1][x];
                    x=who[k][j-1][x];
                }
                who[k][j][i]=x;
                suma[k][j][i]=sum;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(s[i]>=(1<<k))
                dp[k][0][i]=0-s[i];
            else
                dp[k][0][i]=-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<=baza;c++)
                {
                    ll val=-1e9;
                    if(dp[k][j-1][x]>-1e9)
                        val=min(0LL,dp[k][j-1][x]+sum);
                    maxim=max(maxim,val);
                    sum+=suma[k][j-1][x];
                    x=who[k][j-1][x];
                }
                dp[k][j][i]=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][11][x];
                x=who[k][11][x];
            }
            continue;
        }
        for(int i=11;i>=0;i--)
        {
            while(rez+dp[k][i][x]<0)
            {
                rez+=suma[k][i][x];
                x=who[k][i][x];
            }
        }
        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 143 ms 1600848 KB Output is correct
2 Correct 142 ms 1600900 KB Output is correct
3 Correct 155 ms 1607048 KB Output is correct
4 Correct 440 ms 1722708 KB Output is correct
5 Correct 152 ms 1606992 KB Output is correct
6 Correct 425 ms 1722488 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 1602896 KB Output is correct
2 Correct 1581 ms 1946268 KB Output is correct
3 Correct 1404 ms 1946100 KB Output is correct
4 Correct 1472 ms 1947372 KB Output is correct
5 Correct 1765 ms 1947288 KB Output is correct
6 Correct 1432 ms 1945928 KB Output is correct
7 Correct 1527 ms 1944456 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 1602896 KB Output is correct
2 Correct 474 ms 1724016 KB Output is correct
3 Correct 417 ms 1724180 KB Output is correct
4 Correct 375 ms 1723676 KB Output is correct
5 Correct 369 ms 1723552 KB Output is correct
6 Correct 484 ms 1723608 KB Output is correct
7 Correct 510 ms 1723876 KB Output is correct
8 Correct 394 ms 1723388 KB Output is correct
9 Correct 435 ms 1723392 KB Output is correct
10 Correct 404 ms 1723244 KB Output is correct
11 Correct 556 ms 1723732 KB Output is correct
12 Correct 665 ms 1724072 KB Output is correct
13 Correct 490 ms 1723812 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 1602896 KB Output is correct
2 Correct 474 ms 1724016 KB Output is correct
3 Correct 417 ms 1724180 KB Output is correct
4 Correct 375 ms 1723676 KB Output is correct
5 Correct 369 ms 1723552 KB Output is correct
6 Correct 484 ms 1723608 KB Output is correct
7 Correct 510 ms 1723876 KB Output is correct
8 Correct 394 ms 1723388 KB Output is correct
9 Correct 435 ms 1723392 KB Output is correct
10 Correct 404 ms 1723244 KB Output is correct
11 Correct 556 ms 1723732 KB Output is correct
12 Correct 665 ms 1724072 KB Output is correct
13 Correct 490 ms 1723812 KB Output is correct
14 Correct 149 ms 1603060 KB Output is correct
15 Correct 439 ms 1723776 KB Output is correct
16 Correct 490 ms 1723980 KB Output is correct
17 Correct 393 ms 1723816 KB Output is correct
18 Correct 382 ms 1723712 KB Output is correct
19 Correct 485 ms 1723748 KB Output is correct
20 Correct 398 ms 1723528 KB Output is correct
21 Correct 403 ms 1723628 KB Output is correct
22 Correct 425 ms 1723588 KB Output is correct
23 Correct 537 ms 1723732 KB Output is correct
24 Correct 658 ms 1723744 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 1602896 KB Output is correct
2 Correct 474 ms 1724016 KB Output is correct
3 Correct 417 ms 1724180 KB Output is correct
4 Correct 375 ms 1723676 KB Output is correct
5 Correct 369 ms 1723552 KB Output is correct
6 Correct 484 ms 1723608 KB Output is correct
7 Correct 510 ms 1723876 KB Output is correct
8 Correct 394 ms 1723388 KB Output is correct
9 Correct 435 ms 1723392 KB Output is correct
10 Correct 404 ms 1723244 KB Output is correct
11 Correct 556 ms 1723732 KB Output is correct
12 Correct 665 ms 1724072 KB Output is correct
13 Correct 490 ms 1723812 KB Output is correct
14 Correct 149 ms 1603060 KB Output is correct
15 Correct 439 ms 1723776 KB Output is correct
16 Correct 490 ms 1723980 KB Output is correct
17 Correct 393 ms 1723816 KB Output is correct
18 Correct 382 ms 1723712 KB Output is correct
19 Correct 485 ms 1723748 KB Output is correct
20 Correct 398 ms 1723528 KB Output is correct
21 Correct 403 ms 1723628 KB Output is correct
22 Correct 425 ms 1723588 KB Output is correct
23 Correct 537 ms 1723732 KB Output is correct
24 Correct 658 ms 1723744 KB Output is correct
25 Correct 459 ms 1723072 KB Output is correct
26 Correct 466 ms 1724076 KB Output is correct
27 Correct 450 ms 1723492 KB Output is correct
28 Correct 437 ms 1723648 KB Output is correct
29 Correct 481 ms 1724040 KB Output is correct
30 Correct 398 ms 1723928 KB Output is correct
31 Correct 396 ms 1723368 KB Output is correct
32 Correct 594 ms 1723788 KB Output is correct
33 Correct 509 ms 1724148 KB Output is correct
34 Correct 1062 ms 1723544 KB Output is correct
35 Correct 537 ms 1723844 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 1602896 KB Output is correct
2 Correct 1581 ms 1946268 KB Output is correct
3 Correct 1404 ms 1946100 KB Output is correct
4 Correct 1472 ms 1947372 KB Output is correct
5 Correct 1765 ms 1947288 KB Output is correct
6 Correct 1432 ms 1945928 KB Output is correct
7 Correct 1527 ms 1944456 KB Output is correct
8 Correct 150 ms 1602896 KB Output is correct
9 Correct 474 ms 1724016 KB Output is correct
10 Correct 417 ms 1724180 KB Output is correct
11 Correct 375 ms 1723676 KB Output is correct
12 Correct 369 ms 1723552 KB Output is correct
13 Correct 484 ms 1723608 KB Output is correct
14 Correct 510 ms 1723876 KB Output is correct
15 Correct 394 ms 1723388 KB Output is correct
16 Correct 435 ms 1723392 KB Output is correct
17 Correct 404 ms 1723244 KB Output is correct
18 Correct 556 ms 1723732 KB Output is correct
19 Correct 665 ms 1724072 KB Output is correct
20 Correct 490 ms 1723812 KB Output is correct
21 Correct 149 ms 1603060 KB Output is correct
22 Correct 439 ms 1723776 KB Output is correct
23 Correct 490 ms 1723980 KB Output is correct
24 Correct 393 ms 1723816 KB Output is correct
25 Correct 382 ms 1723712 KB Output is correct
26 Correct 485 ms 1723748 KB Output is correct
27 Correct 398 ms 1723528 KB Output is correct
28 Correct 403 ms 1723628 KB Output is correct
29 Correct 425 ms 1723588 KB Output is correct
30 Correct 537 ms 1723732 KB Output is correct
31 Correct 658 ms 1723744 KB Output is correct
32 Correct 459 ms 1723072 KB Output is correct
33 Correct 466 ms 1724076 KB Output is correct
34 Correct 450 ms 1723492 KB Output is correct
35 Correct 437 ms 1723648 KB Output is correct
36 Correct 481 ms 1724040 KB Output is correct
37 Correct 398 ms 1723928 KB Output is correct
38 Correct 396 ms 1723368 KB Output is correct
39 Correct 594 ms 1723788 KB Output is correct
40 Correct 509 ms 1724148 KB Output is correct
41 Correct 1062 ms 1723544 KB Output is correct
42 Correct 537 ms 1723844 KB Output is correct
43 Correct 144 ms 1600848 KB Output is correct
44 Correct 151 ms 1603000 KB Output is correct
45 Correct 2377 ms 1949392 KB Output is correct
46 Correct 1851 ms 1945920 KB Output is correct
47 Correct 1936 ms 1945784 KB Output is correct
48 Correct 1889 ms 1946836 KB Output is correct
49 Correct 2361 ms 1945196 KB Output is correct
50 Correct 1726 ms 1940300 KB Output is correct
51 Correct 1682 ms 1939404 KB Output is correct
52 Correct 1711 ms 1939288 KB Output is correct
53 Correct 2865 ms 1939220 KB Output is correct
54 Correct 1927 ms 1948236 KB Output is correct
55 Correct 2536 ms 1946976 KB Output is correct
56 Correct 2754 ms 1947608 KB Output is correct
57 Correct 2807 ms 1947716 KB Output is correct
58 Correct 2839 ms 1947956 KB Output is correct
59 Correct 2861 ms 1947720 KB Output is correct
60 Correct 2634 ms 1947200 KB Output is correct
61 Correct 2065 ms 1947016 KB Output is correct