oj.uz

답안 #856904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856904 2023-10-04T19:40:04 Z andrei_boaca 던전 (IOI21_dungeons) C++17
89 / 100
 7000 ms 1944732 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];
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][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<=baza;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<=baza;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=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

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 199252 KB Output is correct
2 Correct 20 ms 199472 KB Output is correct
3 Correct 27 ms 207620 KB Output is correct
4 Correct 270 ms 436160 KB Output is correct
5 Correct 27 ms 207668 KB Output is correct
6 Correct 292 ms 435944 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 203572 KB Output is correct
2 Correct 2989 ms 1941624 KB Output is correct
3 Correct 2978 ms 1942784 KB Output is correct
4 Correct 3233 ms 1943488 KB Output is correct
5 Correct 3460 ms 1943376 KB Output is correct
6 Correct 2906 ms 1942252 KB Output is correct
7 Correct 2517 ms 1939764 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 203604 KB Output is correct
2 Correct 340 ms 436288 KB Output is correct
3 Correct 310 ms 435744 KB Output is correct
4 Correct 257 ms 435732 KB Output is correct
5 Correct 262 ms 435792 KB Output is correct
6 Correct 313 ms 435720 KB Output is correct
7 Correct 379 ms 435764 KB Output is correct
8 Correct 264 ms 435860 KB Output is correct
9 Correct 288 ms 435884 KB Output is correct
10 Correct 264 ms 435812 KB Output is correct
11 Correct 420 ms 435900 KB Output is correct
12 Correct 692 ms 435716 KB Output is correct
13 Correct 493 ms 437052 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 203604 KB Output is correct
2 Correct 340 ms 436288 KB Output is correct
3 Correct 310 ms 435744 KB Output is correct
4 Correct 257 ms 435732 KB Output is correct
5 Correct 262 ms 435792 KB Output is correct
6 Correct 313 ms 435720 KB Output is correct
7 Correct 379 ms 435764 KB Output is correct
8 Correct 264 ms 435860 KB Output is correct
9 Correct 288 ms 435884 KB Output is correct
10 Correct 264 ms 435812 KB Output is correct
11 Correct 420 ms 435900 KB Output is correct
12 Correct 692 ms 435716 KB Output is correct
13 Correct 493 ms 437052 KB Output is correct
14 Correct 24 ms 203648 KB Output is correct
15 Correct 292 ms 437308 KB Output is correct
16 Correct 364 ms 437568 KB Output is correct
17 Correct 267 ms 437056 KB Output is correct
18 Correct 276 ms 437056 KB Output is correct
19 Correct 345 ms 437032 KB Output is correct
20 Correct 276 ms 436820 KB Output is correct
21 Correct 286 ms 437108 KB Output is correct
22 Correct 294 ms 436824 KB Output is correct
23 Correct 432 ms 437112 KB Output is correct
24 Correct 513 ms 437184 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 203604 KB Output is correct
2 Correct 340 ms 436288 KB Output is correct
3 Correct 310 ms 435744 KB Output is correct
4 Correct 257 ms 435732 KB Output is correct
5 Correct 262 ms 435792 KB Output is correct
6 Correct 313 ms 435720 KB Output is correct
7 Correct 379 ms 435764 KB Output is correct
8 Correct 264 ms 435860 KB Output is correct
9 Correct 288 ms 435884 KB Output is correct
10 Correct 264 ms 435812 KB Output is correct
11 Correct 420 ms 435900 KB Output is correct
12 Correct 692 ms 435716 KB Output is correct
13 Correct 493 ms 437052 KB Output is correct
14 Correct 24 ms 203648 KB Output is correct
15 Correct 292 ms 437308 KB Output is correct
16 Correct 364 ms 437568 KB Output is correct
17 Correct 267 ms 437056 KB Output is correct
18 Correct 276 ms 437056 KB Output is correct
19 Correct 345 ms 437032 KB Output is correct
20 Correct 276 ms 436820 KB Output is correct
21 Correct 286 ms 437108 KB Output is correct
22 Correct 294 ms 436824 KB Output is correct
23 Correct 432 ms 437112 KB Output is correct
24 Correct 513 ms 437184 KB Output is correct
25 Correct 312 ms 436312 KB Output is correct
26 Correct 332 ms 437572 KB Output is correct
27 Correct 285 ms 436904 KB Output is correct
28 Correct 296 ms 437000 KB Output is correct
29 Correct 351 ms 437524 KB Output is correct
30 Correct 293 ms 437032 KB Output is correct
31 Correct 293 ms 437080 KB Output is correct
32 Correct 461 ms 436820 KB Output is correct
33 Correct 340 ms 437072 KB Output is correct
34 Correct 458 ms 436824 KB Output is correct
35 Correct 397 ms 437016 KB Output is correct

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 203572 KB Output is correct
2 Correct 2989 ms 1941624 KB Output is correct
3 Correct 2978 ms 1942784 KB Output is correct
4 Correct 3233 ms 1943488 KB Output is correct
5 Correct 3460 ms 1943376 KB Output is correct
6 Correct 2906 ms 1942252 KB Output is correct
7 Correct 2517 ms 1939764 KB Output is correct
8 Correct 23 ms 203604 KB Output is correct
9 Correct 340 ms 436288 KB Output is correct
10 Correct 310 ms 435744 KB Output is correct
11 Correct 257 ms 435732 KB Output is correct
12 Correct 262 ms 435792 KB Output is correct
13 Correct 313 ms 435720 KB Output is correct
14 Correct 379 ms 435764 KB Output is correct
15 Correct 264 ms 435860 KB Output is correct
16 Correct 288 ms 435884 KB Output is correct
17 Correct 264 ms 435812 KB Output is correct
18 Correct 420 ms 435900 KB Output is correct
19 Correct 692 ms 435716 KB Output is correct
20 Correct 493 ms 437052 KB Output is correct
21 Correct 24 ms 203648 KB Output is correct
22 Correct 292 ms 437308 KB Output is correct
23 Correct 364 ms 437568 KB Output is correct
24 Correct 267 ms 437056 KB Output is correct
25 Correct 276 ms 437056 KB Output is correct
26 Correct 345 ms 437032 KB Output is correct
27 Correct 276 ms 436820 KB Output is correct
28 Correct 286 ms 437108 KB Output is correct
29 Correct 294 ms 436824 KB Output is correct
30 Correct 432 ms 437112 KB Output is correct
31 Correct 513 ms 437184 KB Output is correct
32 Correct 312 ms 436312 KB Output is correct
33 Correct 332 ms 437572 KB Output is correct
34 Correct 285 ms 436904 KB Output is correct
35 Correct 296 ms 437000 KB Output is correct
36 Correct 351 ms 437524 KB Output is correct
37 Correct 293 ms 437032 KB Output is correct
38 Correct 293 ms 437080 KB Output is correct
39 Correct 461 ms 436820 KB Output is correct
40 Correct 340 ms 437072 KB Output is correct
41 Correct 458 ms 436824 KB Output is correct
42 Correct 397 ms 437016 KB Output is correct
43 Correct 20 ms 199244 KB Output is correct
44 Correct 24 ms 203604 KB Output is correct
45 Correct 4969 ms 1944316 KB Output is correct
46 Correct 3758 ms 1943148 KB Output is correct
47 Correct 3585 ms 1943508 KB Output is correct
48 Correct 3878 ms 1944348 KB Output is correct
49 Correct 5074 ms 1944732 KB Output is correct
50 Correct 3161 ms 1944288 KB Output is correct
51 Correct 3554 ms 1944652 KB Output is correct
52 Correct 3066 ms 1939980 KB Output is correct
53 Execution timed out 7044 ms 1641848 KB Time limit exceeded
54 Halted 0 ms 0 KB -