#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAXS 27 //MAX sparse table
#define MAXI 8 //MAX interval
#define B 3
#define INF 101010101010101010
#define MAX 400400
vector<pll> win, lose; //next
int nxt[MAX][MAXI][MAXS];
ll delta[MAX][MAXI][MAXS], limit[MAX][MAXI][MAXS];
int N;
ll dp[MAX];
ll get(ll x) {
if (x == N) return 0;
if (dp[x]) return dp[x];
return dp[x] = get(win[x].first) + win[x].second;
}
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
ll i;
win.resize(N + 1);
lose.resize(N + 1);
for (i = 0; i < N; i++) {
win[i] = { w[i], s[i] };
lose[i] = { l[i], p[i] };
}
ll k;
for (k = 0; k < MAXI; k++) {
ll low, high;
low = 1 << B * k;
high = 1 << (B * (k + 1));
for (i = 0; i < N; i++) {
if (s[i] < low) {
nxt[i][k][0] = win[i].first;
delta[i][k][0] = win[i].second;
limit[i][k][0] = INF;
}
else if (s[i] >= high) {
nxt[i][k][0] = lose[i].first;
delta[i][k][0] = lose[i].second;
limit[i][k][0] = s[i];
}
else {
nxt[i][k][0] = lose[i].first;
delta[i][k][0] = lose[i].second;
limit[i][k][0] = s[i];
}
}
nxt[N][k][0] = N;
delta[N][k][0] = 0;
limit[N][k][0] = INF;
ll j;
for (j = 1; j < MAXS; j++) {
for (i = 0; i <= N; i++) {
ll v = nxt[i][k][j - 1];
nxt[i][k][j] = nxt[v][k][j - 1];
delta[i][k][j] = delta[i][k][j - 1] + delta[v][k][j - 1];
limit[i][k][j] = max(0LL, min(limit[v][k][j - 1] - delta[i][k][j - 1], limit[i][k][j - 1]));
}
}
}
for (i = 0; i <= N; i++) get(i);
return;
}
void move(int& x, ll& z) {
if (z >= win[x].second) z += win[x].second, x = win[x].first;
else z += lose[x].second, x = lose[x].first;
}
long long simulate(int x, int Z) {
ll z = Z;
ll i;
for (i = 0; i < MAXI; i++) {
if (x == N) break;
if (z >= 10000000) break;
ll high;
high = 1 << (B * (i + 1));
if (high <= z) continue;
if (x == N) return z;
if (z >= 10000000) return z + dp[x];
ll k;
while (z < high) {
for (k = MAXS - 1; k >= 0; k--) {
if (nxt[x][i][k] != N && limit[x][i][k] > z && delta[x][i][k] < 10000000) z += delta[x][i][k], x = nxt[x][i][k];
if (z >= high) break;
}
if (x == N) return z;
if (z >= high) break;
if (x != N && z < high) move(x, z);
}
}
return z + dp[x];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
10 ms |
8916 KB |
Output is correct |
4 |
Correct |
564 ms |
215256 KB |
Output is correct |
5 |
Correct |
13 ms |
8912 KB |
Output is correct |
6 |
Correct |
592 ms |
215296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4556 KB |
Output is correct |
2 |
Correct |
5106 ms |
1727008 KB |
Output is correct |
3 |
Correct |
5120 ms |
1730464 KB |
Output is correct |
4 |
Correct |
4924 ms |
1730688 KB |
Output is correct |
5 |
Correct |
4727 ms |
1720228 KB |
Output is correct |
6 |
Correct |
4846 ms |
1727140 KB |
Output is correct |
7 |
Correct |
4517 ms |
1730656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4556 KB |
Output is correct |
2 |
Correct |
642 ms |
215952 KB |
Output is correct |
3 |
Correct |
583 ms |
216800 KB |
Output is correct |
4 |
Correct |
551 ms |
217340 KB |
Output is correct |
5 |
Correct |
564 ms |
216808 KB |
Output is correct |
6 |
Correct |
630 ms |
216068 KB |
Output is correct |
7 |
Correct |
613 ms |
216040 KB |
Output is correct |
8 |
Correct |
598 ms |
217332 KB |
Output is correct |
9 |
Correct |
555 ms |
216164 KB |
Output is correct |
10 |
Correct |
567 ms |
217316 KB |
Output is correct |
11 |
Correct |
718 ms |
216152 KB |
Output is correct |
12 |
Correct |
858 ms |
216040 KB |
Output is correct |
13 |
Correct |
666 ms |
216160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4556 KB |
Output is correct |
2 |
Correct |
642 ms |
215952 KB |
Output is correct |
3 |
Correct |
583 ms |
216800 KB |
Output is correct |
4 |
Correct |
551 ms |
217340 KB |
Output is correct |
5 |
Correct |
564 ms |
216808 KB |
Output is correct |
6 |
Correct |
630 ms |
216068 KB |
Output is correct |
7 |
Correct |
613 ms |
216040 KB |
Output is correct |
8 |
Correct |
598 ms |
217332 KB |
Output is correct |
9 |
Correct |
555 ms |
216164 KB |
Output is correct |
10 |
Correct |
567 ms |
217316 KB |
Output is correct |
11 |
Correct |
718 ms |
216152 KB |
Output is correct |
12 |
Correct |
858 ms |
216040 KB |
Output is correct |
13 |
Correct |
666 ms |
216160 KB |
Output is correct |
14 |
Correct |
5 ms |
4556 KB |
Output is correct |
15 |
Correct |
584 ms |
216044 KB |
Output is correct |
16 |
Correct |
612 ms |
216152 KB |
Output is correct |
17 |
Correct |
579 ms |
216636 KB |
Output is correct |
18 |
Correct |
553 ms |
216680 KB |
Output is correct |
19 |
Correct |
636 ms |
216036 KB |
Output is correct |
20 |
Correct |
611 ms |
216864 KB |
Output is correct |
21 |
Correct |
605 ms |
216812 KB |
Output is correct |
22 |
Correct |
654 ms |
216296 KB |
Output is correct |
23 |
Correct |
748 ms |
216044 KB |
Output is correct |
24 |
Correct |
895 ms |
216036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4556 KB |
Output is correct |
2 |
Correct |
642 ms |
215952 KB |
Output is correct |
3 |
Correct |
583 ms |
216800 KB |
Output is correct |
4 |
Correct |
551 ms |
217340 KB |
Output is correct |
5 |
Correct |
564 ms |
216808 KB |
Output is correct |
6 |
Correct |
630 ms |
216068 KB |
Output is correct |
7 |
Correct |
613 ms |
216040 KB |
Output is correct |
8 |
Correct |
598 ms |
217332 KB |
Output is correct |
9 |
Correct |
555 ms |
216164 KB |
Output is correct |
10 |
Correct |
567 ms |
217316 KB |
Output is correct |
11 |
Correct |
718 ms |
216152 KB |
Output is correct |
12 |
Correct |
858 ms |
216040 KB |
Output is correct |
13 |
Correct |
666 ms |
216160 KB |
Output is correct |
14 |
Correct |
5 ms |
4556 KB |
Output is correct |
15 |
Correct |
584 ms |
216044 KB |
Output is correct |
16 |
Correct |
612 ms |
216152 KB |
Output is correct |
17 |
Correct |
579 ms |
216636 KB |
Output is correct |
18 |
Correct |
553 ms |
216680 KB |
Output is correct |
19 |
Correct |
636 ms |
216036 KB |
Output is correct |
20 |
Correct |
611 ms |
216864 KB |
Output is correct |
21 |
Correct |
605 ms |
216812 KB |
Output is correct |
22 |
Correct |
654 ms |
216296 KB |
Output is correct |
23 |
Correct |
748 ms |
216044 KB |
Output is correct |
24 |
Correct |
895 ms |
216036 KB |
Output is correct |
25 |
Correct |
606 ms |
215264 KB |
Output is correct |
26 |
Correct |
627 ms |
216004 KB |
Output is correct |
27 |
Correct |
555 ms |
216036 KB |
Output is correct |
28 |
Correct |
570 ms |
216040 KB |
Output is correct |
29 |
Correct |
607 ms |
216036 KB |
Output is correct |
30 |
Correct |
628 ms |
217320 KB |
Output is correct |
31 |
Correct |
618 ms |
217324 KB |
Output is correct |
32 |
Correct |
848 ms |
216164 KB |
Output is correct |
33 |
Correct |
949 ms |
215956 KB |
Output is correct |
34 |
Correct |
1440 ms |
216004 KB |
Output is correct |
35 |
Correct |
834 ms |
216036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4556 KB |
Output is correct |
2 |
Correct |
5106 ms |
1727008 KB |
Output is correct |
3 |
Correct |
5120 ms |
1730464 KB |
Output is correct |
4 |
Correct |
4924 ms |
1730688 KB |
Output is correct |
5 |
Correct |
4727 ms |
1720228 KB |
Output is correct |
6 |
Correct |
4846 ms |
1727140 KB |
Output is correct |
7 |
Correct |
4517 ms |
1730656 KB |
Output is correct |
8 |
Correct |
5 ms |
4556 KB |
Output is correct |
9 |
Correct |
642 ms |
215952 KB |
Output is correct |
10 |
Correct |
583 ms |
216800 KB |
Output is correct |
11 |
Correct |
551 ms |
217340 KB |
Output is correct |
12 |
Correct |
564 ms |
216808 KB |
Output is correct |
13 |
Correct |
630 ms |
216068 KB |
Output is correct |
14 |
Correct |
613 ms |
216040 KB |
Output is correct |
15 |
Correct |
598 ms |
217332 KB |
Output is correct |
16 |
Correct |
555 ms |
216164 KB |
Output is correct |
17 |
Correct |
567 ms |
217316 KB |
Output is correct |
18 |
Correct |
718 ms |
216152 KB |
Output is correct |
19 |
Correct |
858 ms |
216040 KB |
Output is correct |
20 |
Correct |
666 ms |
216160 KB |
Output is correct |
21 |
Correct |
5 ms |
4556 KB |
Output is correct |
22 |
Correct |
584 ms |
216044 KB |
Output is correct |
23 |
Correct |
612 ms |
216152 KB |
Output is correct |
24 |
Correct |
579 ms |
216636 KB |
Output is correct |
25 |
Correct |
553 ms |
216680 KB |
Output is correct |
26 |
Correct |
636 ms |
216036 KB |
Output is correct |
27 |
Correct |
611 ms |
216864 KB |
Output is correct |
28 |
Correct |
605 ms |
216812 KB |
Output is correct |
29 |
Correct |
654 ms |
216296 KB |
Output is correct |
30 |
Correct |
748 ms |
216044 KB |
Output is correct |
31 |
Correct |
895 ms |
216036 KB |
Output is correct |
32 |
Correct |
606 ms |
215264 KB |
Output is correct |
33 |
Correct |
627 ms |
216004 KB |
Output is correct |
34 |
Correct |
555 ms |
216036 KB |
Output is correct |
35 |
Correct |
570 ms |
216040 KB |
Output is correct |
36 |
Correct |
607 ms |
216036 KB |
Output is correct |
37 |
Correct |
628 ms |
217320 KB |
Output is correct |
38 |
Correct |
618 ms |
217324 KB |
Output is correct |
39 |
Correct |
848 ms |
216164 KB |
Output is correct |
40 |
Correct |
949 ms |
215956 KB |
Output is correct |
41 |
Correct |
1440 ms |
216004 KB |
Output is correct |
42 |
Correct |
834 ms |
216036 KB |
Output is correct |
43 |
Correct |
0 ms |
332 KB |
Output is correct |
44 |
Correct |
5 ms |
4556 KB |
Output is correct |
45 |
Correct |
6356 ms |
1720112 KB |
Output is correct |
46 |
Correct |
4682 ms |
1720144 KB |
Output is correct |
47 |
Correct |
4733 ms |
1720344 KB |
Output is correct |
48 |
Correct |
4661 ms |
1726992 KB |
Output is correct |
49 |
Correct |
6545 ms |
1720076 KB |
Output is correct |
50 |
Correct |
4938 ms |
1726940 KB |
Output is correct |
51 |
Correct |
4550 ms |
1725276 KB |
Output is correct |
52 |
Correct |
4848 ms |
1726948 KB |
Output is correct |
53 |
Execution timed out |
7158 ms |
1716956 KB |
Time limit exceeded |
54 |
Halted |
0 ms |
0 KB |
- |