oj.uz

답안 #856884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856884 2023-10-04T18:52:36 Z andrei_boaca 던전 (IOI21_dungeons) C++17
11 / 100
 7000 ms 451672 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[24][400005];
ll n;
int dp[24][400005][12];
ll suma[24][400005][12];
int who[24][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<24;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<24;i++)
            if((1<<i)<rez)
                k=i;
        if(k==23)
        {
            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 20 ms 205404 KB Output is correct
2 Correct 19 ms 205640 KB Output is correct
3 Correct 30 ms 213956 KB Output is correct
4 Correct 337 ms 450404 KB Output is correct
5 Correct 29 ms 213952 KB Output is correct
6 Correct 324 ms 450328 KB Output is correct

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 7033 ms 209756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 209812 KB Output is correct
2 Correct 389 ms 450228 KB Output is correct
3 Correct 329 ms 450328 KB Output is correct
4 Correct 283 ms 451452 KB Output is correct
5 Correct 290 ms 451324 KB Output is correct
6 Correct 417 ms 451548 KB Output is correct
7 Correct 380 ms 451376 KB Output is correct
8 Correct 299 ms 451156 KB Output is correct
9 Correct 323 ms 451292 KB Output is correct
10 Correct 298 ms 451148 KB Output is correct
11 Correct 494 ms 451672 KB Output is correct
12 Execution timed out 7023 ms 451552 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 209812 KB Output is correct
2 Correct 389 ms 450228 KB Output is correct
3 Correct 329 ms 450328 KB Output is correct
4 Correct 283 ms 451452 KB Output is correct
5 Correct 290 ms 451324 KB Output is correct
6 Correct 417 ms 451548 KB Output is correct
7 Correct 380 ms 451376 KB Output is correct
8 Correct 299 ms 451156 KB Output is correct
9 Correct 323 ms 451292 KB Output is correct
10 Correct 298 ms 451148 KB Output is correct
11 Correct 494 ms 451672 KB Output is correct
12 Execution timed out 7023 ms 451552 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 209812 KB Output is correct
2 Correct 389 ms 450228 KB Output is correct
3 Correct 329 ms 450328 KB Output is correct
4 Correct 283 ms 451452 KB Output is correct
5 Correct 290 ms 451324 KB Output is correct
6 Correct 417 ms 451548 KB Output is correct
7 Correct 380 ms 451376 KB Output is correct
8 Correct 299 ms 451156 KB Output is correct
9 Correct 323 ms 451292 KB Output is correct
10 Correct 298 ms 451148 KB Output is correct
11 Correct 494 ms 451672 KB Output is correct
12 Execution timed out 7023 ms 451552 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 7033 ms 209756 KB Time limit exceeded
2 Halted 0 ms 0 KB -