oj.uz

답안 #981440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981440 2024-05-13T08:13:13 Z 12345678 던전 (IOI21_dungeons) C++17
37 / 100
 7000 ms 1911332 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=4e5+5, lx=8, kx=25;

ll N, pw[20];
vector<ll> S(nx), P(nx), W(nx), L(nx);

struct edge
{
    ll out, cost, t;
    edge(ll out=0, ll cost=0, ll t=0): out(out), cost(cost), t(t){}
} dp[lx][nx][kx];

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
    N=n;
    pw[0]=1;
    for (int i=1; i<20; i++) pw[i]=pw[i-1]*8;
    for (int i=0; i<n; i++) S[i]=s[i], P[i]=p[i], W[i]=w[i], L[i]=l[i];
    W[n]=L[n]=n;
    for (int i=0; i<lx; i++)
    {
        for (int u=0; u<=n; u++)
        {
            if (s[u]<=pw[i]) dp[i][u][0]=edge(W[u], S[u], 1e18);
            else dp[i][u][0]=edge(L[u], P[u], S[u]);
        }
        for (int j=1; j<kx; j++)
        {
            for (int u=0; u<=n; u++)
            {
                int v=dp[i][u][j-1].out;
                ll out=dp[i][v][j-1].out;
                ll cost=dp[i][u][j-1].cost+dp[i][v][j-1].cost;
                ll t=min(dp[i][u][j-1].t, dp[i][v][j-1].t-dp[i][u][j-1].cost);
                dp[i][u][j]=edge(out, cost, t);
            }
        }
    }
}

long long simulate(int x, int z) {
    ll cur=z, st=0;
    while (x!=N)
    {
        //cout<<"debug "<<x<<' '<<cur<<' '<<st<<'\n';
        while (st+1<lx&&pw[st+1]<=cur) st++;
        for (int cnt=0; cnt<3; cnt++)
        {
            for (int i=kx-1; i>=0; i--) if (dp[st][x][i].t>cur) cur+=dp[st][x][i].cost, x=dp[st][x][i].out; //cout<<"here "<<i<<' '<<cur<<' '<<x<<'\n';
            //cout<<"after "<<x<<' '<<cur<<' '<<st<<'\n';
            if (cur>=S[x]) cur+=S[x], x=W[x];
            else cur+=P[x], x=L[x];
        }
    }
	return cur;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1085 ms 1891660 KB Output is correct
2 Correct 642 ms 1891656 KB Output is correct
3 Correct 637 ms 1891744 KB Output is correct
4 Correct 704 ms 1894268 KB Output is correct
5 Correct 610 ms 1891592 KB Output is correct
6 Correct 682 ms 1894016 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 624 ms 1891656 KB Output is correct
2 Correct 2295 ms 1911332 KB Output is correct
3 Correct 2161 ms 1907092 KB Output is correct
4 Correct 2156 ms 1908888 KB Output is correct
5 Correct 2181 ms 1910428 KB Output is correct
6 Correct 2393 ms 1910348 KB Output is correct
7 Correct 2225 ms 1909072 KB Output is correct

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 1891668 KB Output is correct
2 Correct 750 ms 1895628 KB Output is correct
3 Execution timed out 7090 ms 1895764 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 1891668 KB Output is correct
2 Correct 750 ms 1895628 KB Output is correct
3 Execution timed out 7090 ms 1895764 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 1891668 KB Output is correct
2 Correct 750 ms 1895628 KB Output is correct
3 Execution timed out 7090 ms 1895764 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 624 ms 1891656 KB Output is correct
2 Correct 2295 ms 1911332 KB Output is correct
3 Correct 2161 ms 1907092 KB Output is correct
4 Correct 2156 ms 1908888 KB Output is correct
5 Correct 2181 ms 1910428 KB Output is correct
6 Correct 2393 ms 1910348 KB Output is correct
7 Correct 2225 ms 1909072 KB Output is correct
8 Correct 606 ms 1891668 KB Output is correct
9 Correct 750 ms 1895628 KB Output is correct
10 Execution timed out 7090 ms 1895764 KB Time limit exceeded
11 Halted 0 ms 0 KB -