oj.uz

Submission #445298

# Submission time Handle Problem Language Result Execution time Memory
445298 2021-07-17T10:58:46 Z BaraaArmoush Dungeons Game (IOI21_dungeons) C++17
25 / 100
 480 ms 297396 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int M = 10;
const int K = 40;
const int N = 50500;

int n, m;
int s[N];
int p[N];
int w[N];
int l[N];
int us[M];

int dp1[M][K][N];
ll dp2[M][K][N];

void init(int n, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
    ::n = n;
    copy(S.begin(), S.end(), s);
    copy(P.begin(), P.end(), p);
    copy(W.begin(), W.end(), w);
    copy(L.begin(), L.end(), l);

    sort(S.begin(), S.end());
    S.erase(unique(S.begin(), S.end()), S.end());
    S.insert(S.begin(), 0);
    copy(S.begin(), S.end(), us);
    m = S.size();

    w[n] = l[n] = n;

    for (int r = 0; r < m; r++) {
        for (int i = 0; i <= n; i++) {
            if (S[r] < s[i]) {
                dp1[r][0][i] = l[i];
                dp2[r][0][i] = p[i];
            } else {
                dp1[r][0][i] = w[i];
                dp2[r][0][i] = s[i];
            }
        }

        for (int j = 1; j < K; j++) {
            for (int i = 0; i <= n; i++) {
                dp1[r][j][i] = dp1[r][j - 1][dp1[r][j - 1][i]];
                dp2[r][j][i] = dp2[r][j - 1][i] + dp2[r][j - 1][dp1[r][j - 1][i]];
            }
        }
    }
}

ll simulate(int i, int z) {
    ll x = z;

    for (int r = 0; r < m; r++) {
        for (int j = K - 1; ~j; --j) {
            if (r + 1 == m || x + dp2[r][j][i] < us[r + 1]) {
                x += dp2[r][j][i];
                i = dp1[r][j][i];
            }

            if (x < us[r + 1]) {
                x += dp2[r][0][i];
                i = dp1[r][0][i];
            }
        }
    }

    return x;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Runtime error 25 ms 7848 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 10852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2044 KB Output is correct
2 Correct 144 ms 50756 KB Output is correct
3 Correct 147 ms 50764 KB Output is correct
4 Correct 134 ms 50756 KB Output is correct
5 Correct 134 ms 50760 KB Output is correct
6 Correct 153 ms 50752 KB Output is correct
7 Correct 158 ms 50768 KB Output is correct
8 Correct 137 ms 50772 KB Output is correct
9 Correct 135 ms 50796 KB Output is correct
10 Correct 133 ms 50768 KB Output is correct
11 Correct 105 ms 50764 KB Output is correct
12 Correct 206 ms 50792 KB Output is correct
13 Correct 172 ms 50756 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2044 KB Output is correct
2 Correct 144 ms 50756 KB Output is correct
3 Correct 147 ms 50764 KB Output is correct
4 Correct 134 ms 50756 KB Output is correct
5 Correct 134 ms 50760 KB Output is correct
6 Correct 153 ms 50752 KB Output is correct
7 Correct 158 ms 50768 KB Output is correct
8 Correct 137 ms 50772 KB Output is correct
9 Correct 135 ms 50796 KB Output is correct
10 Correct 133 ms 50768 KB Output is correct
11 Correct 105 ms 50764 KB Output is correct
12 Correct 206 ms 50792 KB Output is correct
13 Correct 172 ms 50756 KB Output is correct
14 Correct 5 ms 4428 KB Output is correct
15 Correct 283 ms 99760 KB Output is correct
16 Correct 372 ms 123652 KB Output is correct
17 Correct 441 ms 146864 KB Output is correct
18 Correct 480 ms 146864 KB Output is correct
19 Correct 369 ms 147024 KB Output is correct
20 Correct 283 ms 99268 KB Output is correct
21 Correct 376 ms 123204 KB Output is correct
22 Correct 189 ms 75720 KB Output is correct
23 Correct 309 ms 123328 KB Output is correct
24 Correct 392 ms 99520 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2044 KB Output is correct
2 Correct 144 ms 50756 KB Output is correct
3 Correct 147 ms 50764 KB Output is correct
4 Correct 134 ms 50756 KB Output is correct
5 Correct 134 ms 50760 KB Output is correct
6 Correct 153 ms 50752 KB Output is correct
7 Correct 158 ms 50768 KB Output is correct
8 Correct 137 ms 50772 KB Output is correct
9 Correct 135 ms 50796 KB Output is correct
10 Correct 133 ms 50768 KB Output is correct
11 Correct 105 ms 50764 KB Output is correct
12 Correct 206 ms 50792 KB Output is correct
13 Correct 172 ms 50756 KB Output is correct
14 Correct 5 ms 4428 KB Output is correct
15 Correct 283 ms 99760 KB Output is correct
16 Correct 372 ms 123652 KB Output is correct
17 Correct 441 ms 146864 KB Output is correct
18 Correct 480 ms 146864 KB Output is correct
19 Correct 369 ms 147024 KB Output is correct
20 Correct 283 ms 99268 KB Output is correct
21 Correct 376 ms 123204 KB Output is correct
22 Correct 189 ms 75720 KB Output is correct
23 Correct 309 ms 123328 KB Output is correct
24 Correct 392 ms 99520 KB Output is correct
25 Runtime error 313 ms 297396 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 10852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -