oj.uz

답안 #856876

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856876 2023-10-04T18:31:46 Z andrei_boaca 던전 (IOI21_dungeons) C++17
37 / 100
 3998 ms 1912884 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++)
                {
                    maxim=max(maxim,min(0LL,dp[k][x][j-1]+sum));
                    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;
        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 19 ms 205400 KB Output is correct
2 Correct 18 ms 205488 KB Output is correct
3 Correct 27 ms 213848 KB Output is correct
4 Correct 295 ms 450552 KB Output is correct
5 Correct 29 ms 213844 KB Output is correct
6 Correct 317 ms 450300 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 209756 KB Output is correct
2 Correct 3925 ms 1909116 KB Output is correct
3 Correct 3315 ms 1911860 KB Output is correct
4 Correct 3505 ms 1912768 KB Output is correct
5 Correct 3998 ms 1912884 KB Output is correct
6 Correct 3810 ms 1911280 KB Output is correct
7 Correct 2997 ms 1909056 KB Output is correct

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 209756 KB Output is correct
2 Correct 356 ms 450252 KB Output is correct
3 Runtime error 350 ms 569980 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 209756 KB Output is correct
2 Correct 356 ms 450252 KB Output is correct
3 Runtime error 350 ms 569980 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 209756 KB Output is correct
2 Correct 356 ms 450252 KB Output is correct
3 Runtime error 350 ms 569980 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 209756 KB Output is correct
2 Correct 3925 ms 1909116 KB Output is correct
3 Correct 3315 ms 1911860 KB Output is correct
4 Correct 3505 ms 1912768 KB Output is correct
5 Correct 3998 ms 1912884 KB Output is correct
6 Correct 3810 ms 1911280 KB Output is correct
7 Correct 2997 ms 1909056 KB Output is correct
8 Correct 24 ms 209756 KB Output is correct
9 Correct 356 ms 450252 KB Output is correct
10 Runtime error 350 ms 569980 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -