oj.uz

답안 #856903

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856903 2023-10-04T19:38:45 Z andrei_boaca 던전 (IOI21_dungeons) C++17
37 / 100
 7000 ms 1947060 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];
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<=11;j++)
        {
            for(int i=0;i<=n;i++)
            {
                ll sum=0;
                ll x=i;
                for(int c=1;c<=2;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<=2;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 19 ms 199256 KB Output is correct
2 Correct 19 ms 199256 KB Output is correct
3 Correct 22 ms 207708 KB Output is correct
4 Correct 147 ms 436040 KB Output is correct
5 Correct 23 ms 207708 KB Output is correct
6 Correct 144 ms 436048 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 203864 KB Output is correct
2 Correct 2686 ms 1944644 KB Output is correct
3 Correct 2587 ms 1945496 KB Output is correct
4 Correct 2643 ms 1947060 KB Output is correct
5 Correct 2375 ms 1947008 KB Output is correct
6 Correct 2611 ms 1945744 KB Output is correct
7 Correct 2293 ms 1944408 KB Output is correct

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 203864 KB Output is correct
2 Correct 177 ms 437572 KB Output is correct
3 Correct 179 ms 437572 KB Output is correct
4 Correct 195 ms 437072 KB Output is correct
5 Correct 176 ms 436820 KB Output is correct
6 Correct 194 ms 437052 KB Output is correct
7 Correct 746 ms 437096 KB Output is correct
8 Correct 242 ms 436744 KB Output is correct
9 Correct 166 ms 436712 KB Output is correct
10 Correct 226 ms 436616 KB Output is correct
11 Correct 253 ms 437072 KB Output is correct
12 Execution timed out 7063 ms 437076 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 203864 KB Output is correct
2 Correct 177 ms 437572 KB Output is correct
3 Correct 179 ms 437572 KB Output is correct
4 Correct 195 ms 437072 KB Output is correct
5 Correct 176 ms 436820 KB Output is correct
6 Correct 194 ms 437052 KB Output is correct
7 Correct 746 ms 437096 KB Output is correct
8 Correct 242 ms 436744 KB Output is correct
9 Correct 166 ms 436712 KB Output is correct
10 Correct 226 ms 436616 KB Output is correct
11 Correct 253 ms 437072 KB Output is correct
12 Execution timed out 7063 ms 437076 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 203864 KB Output is correct
2 Correct 177 ms 437572 KB Output is correct
3 Correct 179 ms 437572 KB Output is correct
4 Correct 195 ms 437072 KB Output is correct
5 Correct 176 ms 436820 KB Output is correct
6 Correct 194 ms 437052 KB Output is correct
7 Correct 746 ms 437096 KB Output is correct
8 Correct 242 ms 436744 KB Output is correct
9 Correct 166 ms 436712 KB Output is correct
10 Correct 226 ms 436616 KB Output is correct
11 Correct 253 ms 437072 KB Output is correct
12 Execution timed out 7063 ms 437076 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 203864 KB Output is correct
2 Correct 2686 ms 1944644 KB Output is correct
3 Correct 2587 ms 1945496 KB Output is correct
4 Correct 2643 ms 1947060 KB Output is correct
5 Correct 2375 ms 1947008 KB Output is correct
6 Correct 2611 ms 1945744 KB Output is correct
7 Correct 2293 ms 1944408 KB Output is correct
8 Correct 22 ms 203864 KB Output is correct
9 Correct 177 ms 437572 KB Output is correct
10 Correct 179 ms 437572 KB Output is correct
11 Correct 195 ms 437072 KB Output is correct
12 Correct 176 ms 436820 KB Output is correct
13 Correct 194 ms 437052 KB Output is correct
14 Correct 746 ms 437096 KB Output is correct
15 Correct 242 ms 436744 KB Output is correct
16 Correct 166 ms 436712 KB Output is correct
17 Correct 226 ms 436616 KB Output is correct
18 Correct 253 ms 437072 KB Output is correct
19 Execution timed out 7063 ms 437076 KB Time limit exceeded
20 Halted 0 ms 0 KB -