oj.uz

Submission #442839

# Submission time Handle Problem Language Result Execution time Memory
442839 2021-07-09T08:34:42 Z baluteshih Dungeons Game (IOI21_dungeons) C++17
25 / 100
 239 ms 116936 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 = 100;
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 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 7 ms 8652 KB Output is correct
4 Incorrect 27 ms 3076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 101 ms 41476 KB Output is correct
3 Correct 119 ms 41408 KB Output is correct
4 Correct 83 ms 41432 KB Output is correct
5 Correct 86 ms 41456 KB Output is correct
6 Correct 120 ms 41536 KB Output is correct
7 Correct 103 ms 41492 KB Output is correct
8 Correct 86 ms 41440 KB Output is correct
9 Correct 94 ms 41484 KB Output is correct
10 Correct 82 ms 41480 KB Output is correct
11 Correct 97 ms 41484 KB Output is correct
12 Correct 189 ms 41460 KB Output is correct
13 Correct 187 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 101 ms 41476 KB Output is correct
3 Correct 119 ms 41408 KB Output is correct
4 Correct 83 ms 41432 KB Output is correct
5 Correct 86 ms 41456 KB Output is correct
6 Correct 120 ms 41536 KB Output is correct
7 Correct 103 ms 41492 KB Output is correct
8 Correct 86 ms 41440 KB Output is correct
9 Correct 94 ms 41484 KB Output is correct
10 Correct 82 ms 41480 KB Output is correct
11 Correct 97 ms 41484 KB Output is correct
12 Correct 189 ms 41460 KB Output is correct
13 Correct 187 ms 41416 KB Output is correct
14 Correct 3 ms 2252 KB Output is correct
15 Correct 122 ms 79312 KB Output is correct
16 Correct 172 ms 98084 KB Output is correct
17 Correct 135 ms 116932 KB Output is correct
18 Correct 184 ms 116936 KB Output is correct
19 Correct 208 ms 116876 KB Output is correct
20 Correct 150 ms 79176 KB Output is correct
21 Correct 192 ms 98012 KB Output is correct
22 Correct 127 ms 60356 KB Output is correct
23 Correct 165 ms 97984 KB Output is correct
24 Correct 239 ms 79124 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 101 ms 41476 KB Output is correct
3 Correct 119 ms 41408 KB Output is correct
4 Correct 83 ms 41432 KB Output is correct
5 Correct 86 ms 41456 KB Output is correct
6 Correct 120 ms 41536 KB Output is correct
7 Correct 103 ms 41492 KB Output is correct
8 Correct 86 ms 41440 KB Output is correct
9 Correct 94 ms 41484 KB Output is correct
10 Correct 82 ms 41480 KB Output is correct
11 Correct 97 ms 41484 KB Output is correct
12 Correct 189 ms 41460 KB Output is correct
13 Correct 187 ms 41416 KB Output is correct
14 Correct 3 ms 2252 KB Output is correct
15 Correct 122 ms 79312 KB Output is correct
16 Correct 172 ms 98084 KB Output is correct
17 Correct 135 ms 116932 KB Output is correct
18 Correct 184 ms 116936 KB Output is correct
19 Correct 208 ms 116876 KB Output is correct
20 Correct 150 ms 79176 KB Output is correct
21 Correct 192 ms 98012 KB Output is correct
22 Correct 127 ms 60356 KB Output is correct
23 Correct 165 ms 97984 KB Output is correct
24 Correct 239 ms 79124 KB Output is correct
25 Incorrect 28 ms 3088 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 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -