oj.uz

Submission #442838

# Submission time Handle Problem Language Result Execution time Memory
442838 2021-07-09T08:34:19 Z baluteshih Dungeons Game (IOI21_dungeons) C++17
25 / 100
 252 ms 116800 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

struct node {
    int to;
    ll sum;
    node operator+(const node &a) const {
        return node{a.to, sum + a.sum};
    }
};

const int K = 7;
int N, lg = __lg(10000000);
vector<int> S, P, W, L;
vector<int> val;
vector<node> dp[K][30];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    N = n, S = s, P = p, W = w, L = l;
    for (int i : S)
        val.pb(i);
    val.pb(0);
    sort(ALL(val)), val.resize(unique(ALL(val)) - val.begin());
    if (SZ(val) >= K)
        return;
    for (int i = 0; i < SZ(val); ++i) {
        dp[i][0].resize(N + 1);
        dp[i][0][N] = node{N, 0LL};
        for (int j = 0; j < N; ++j)
            if (val[i] >= S[j])
                dp[i][0][j] = node{W[j], (ll)S[j]};
            else
                dp[i][0][j] = node{L[j], (ll)P[j]};
        for (int j = 1; j <= lg; ++j) {
            dp[i][j].resize(N + 1);
            for (int k = 0; k <= N; ++k)
                dp[i][j][k] = dp[i][j - 1][k] + dp[i][j - 1][dp[i][j - 1][k].to]; 
        }
    }
	return;
}

long long simulate(int x, int z) {
	if (SZ(val) >= K)
        return 0;
    int p;
    ll nw = z;
    for (p = 0; p < SZ(val);) {
        while (p + 1 < SZ(val) && nw >= val[p + 1])
            ++p;
        if (p == SZ(val) - 1 || (dp[p][lg][x].to == N && nw + dp[p][lg][x].sum < val[p + 1]))
            break;
        for (int i = lg; i >= 0; --i)
            if (nw + dp[p][i][x].sum < val[p + 1]) {
                nw += dp[p][i][x].sum;
                x = dp[p][i][x].to;
            }
        nw += dp[p][0][x].sum;
        x = dp[p][0][x].to;
    }
    for (int i = lg; i >= 0; --i)
        if (dp[p][i][x].to != N) {
            nw += dp[p][i][x].sum;
            x = dp[p][i][x].to;
        }
    nw += dp[p][0][x].sum;
    return nw;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 114 ms 41412 KB Output is correct
3 Correct 103 ms 41416 KB Output is correct
4 Correct 83 ms 41400 KB Output is correct
5 Correct 86 ms 41412 KB Output is correct
6 Correct 113 ms 41392 KB Output is correct
7 Correct 103 ms 41408 KB Output is correct
8 Correct 84 ms 41416 KB Output is correct
9 Correct 93 ms 41408 KB Output is correct
10 Correct 107 ms 41408 KB Output is correct
11 Correct 96 ms 41412 KB Output is correct
12 Correct 172 ms 41416 KB Output is correct
13 Correct 161 ms 41416 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 114 ms 41412 KB Output is correct
3 Correct 103 ms 41416 KB Output is correct
4 Correct 83 ms 41400 KB Output is correct
5 Correct 86 ms 41412 KB Output is correct
6 Correct 113 ms 41392 KB Output is correct
7 Correct 103 ms 41408 KB Output is correct
8 Correct 84 ms 41416 KB Output is correct
9 Correct 93 ms 41408 KB Output is correct
10 Correct 107 ms 41408 KB Output is correct
11 Correct 96 ms 41412 KB Output is correct
12 Correct 172 ms 41416 KB Output is correct
13 Correct 161 ms 41416 KB Output is correct
14 Correct 3 ms 2252 KB Output is correct
15 Correct 143 ms 79048 KB Output is correct
16 Correct 150 ms 97952 KB Output is correct
17 Correct 140 ms 116768 KB Output is correct
18 Correct 197 ms 116800 KB Output is correct
19 Correct 206 ms 116768 KB Output is correct
20 Correct 162 ms 79168 KB Output is correct
21 Correct 195 ms 97992 KB Output is correct
22 Correct 123 ms 60224 KB Output is correct
23 Correct 154 ms 97916 KB Output is correct
24 Correct 252 ms 79040 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 114 ms 41412 KB Output is correct
3 Correct 103 ms 41416 KB Output is correct
4 Correct 83 ms 41400 KB Output is correct
5 Correct 86 ms 41412 KB Output is correct
6 Correct 113 ms 41392 KB Output is correct
7 Correct 103 ms 41408 KB Output is correct
8 Correct 84 ms 41416 KB Output is correct
9 Correct 93 ms 41408 KB Output is correct
10 Correct 107 ms 41408 KB Output is correct
11 Correct 96 ms 41412 KB Output is correct
12 Correct 172 ms 41416 KB Output is correct
13 Correct 161 ms 41416 KB Output is correct
14 Correct 3 ms 2252 KB Output is correct
15 Correct 143 ms 79048 KB Output is correct
16 Correct 150 ms 97952 KB Output is correct
17 Correct 140 ms 116768 KB Output is correct
18 Correct 197 ms 116800 KB Output is correct
19 Correct 206 ms 116768 KB Output is correct
20 Correct 162 ms 79168 KB Output is correct
21 Correct 195 ms 97992 KB Output is correct
22 Correct 123 ms 60224 KB Output is correct
23 Correct 154 ms 97916 KB Output is correct
24 Correct 252 ms 79040 KB Output is correct
25 Incorrect 28 ms 3028 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -