oj.uz

Submission #442822

# Submission time Handle Problem Language Result Execution time Memory
442822 2021-07-09T07:56:55 Z baluteshih Dungeons Game (IOI21_dungeons) C++17
13 / 100
 184 ms 97920 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};
    }
};

int N, lg = __lg(10000000);
vector<int> S, P, W, L;
vector<int> val;
vector<node> dp[10][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) > 6) {
        assert(0);
        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) > 6)
        return 0;
    int p;
    ll nw = z;
    for (p = 0; p < SZ(val);) {
        while (p + 1 < SZ(val) && nw >= val[p + 1])
            ++p;
        if (dp[p][lg][x].to == N)
            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 268 KB Output is correct
2 Runtime error 1 ms 460 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1124 KB Output is correct
2 Correct 103 ms 41416 KB Output is correct
3 Correct 114 ms 41416 KB Output is correct
4 Correct 87 ms 41360 KB Output is correct
5 Correct 89 ms 41340 KB Output is correct
6 Correct 118 ms 41464 KB Output is correct
7 Correct 102 ms 41420 KB Output is correct
8 Correct 95 ms 41544 KB Output is correct
9 Correct 99 ms 41416 KB Output is correct
10 Correct 89 ms 41424 KB Output is correct
11 Correct 99 ms 41508 KB Output is correct
12 Correct 184 ms 41416 KB Output is correct
13 Correct 171 ms 41408 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1124 KB Output is correct
2 Correct 103 ms 41416 KB Output is correct
3 Correct 114 ms 41416 KB Output is correct
4 Correct 87 ms 41360 KB Output is correct
5 Correct 89 ms 41340 KB Output is correct
6 Correct 118 ms 41464 KB Output is correct
7 Correct 102 ms 41420 KB Output is correct
8 Correct 95 ms 41544 KB Output is correct
9 Correct 99 ms 41416 KB Output is correct
10 Correct 89 ms 41424 KB Output is correct
11 Correct 99 ms 41508 KB Output is correct
12 Correct 184 ms 41416 KB Output is correct
13 Correct 171 ms 41408 KB Output is correct
14 Correct 3 ms 2252 KB Output is correct
15 Correct 126 ms 79076 KB Output is correct
16 Incorrect 150 ms 97920 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1124 KB Output is correct
2 Correct 103 ms 41416 KB Output is correct
3 Correct 114 ms 41416 KB Output is correct
4 Correct 87 ms 41360 KB Output is correct
5 Correct 89 ms 41340 KB Output is correct
6 Correct 118 ms 41464 KB Output is correct
7 Correct 102 ms 41420 KB Output is correct
8 Correct 95 ms 41544 KB Output is correct
9 Correct 99 ms 41416 KB Output is correct
10 Correct 89 ms 41424 KB Output is correct
11 Correct 99 ms 41508 KB Output is correct
12 Correct 184 ms 41416 KB Output is correct
13 Correct 171 ms 41408 KB Output is correct
14 Correct 3 ms 2252 KB Output is correct
15 Correct 126 ms 79076 KB Output is correct
16 Incorrect 150 ms 97920 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -