#pragma GCC optimize("Ofast")
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
constexpr int Base = 26, LN = 25, LS = 6, N = 4e5 + 5;
using ll = long long;
constexpr ll inf = 1e18;
int n;
int go[LS][LN][N];
ll lim[LS][LN][N], gain[LS][LN][N], pw[LS];
vector<int> s, p, win, lose;
void init(int _n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n = _n, s = S, p = P, win = W, lose = L;
for (int i = pw[0] = 1; i < LS; i++) {
pw[i] = pw[i - 1] * Base;
}
for (int C = 0; C < LS; C++) {
for (int i = 0; i < n; i++) {
if (pw[C] >= s[i]) {
if (win[i] == n) {
go[C][0][i] = -1;
} else {
go[C][0][i] = win[i];
gain[C][0][i] = s[i];
lim[C][0][i] = inf;
}
} else {
if (lose[i] == n) {
go[C][0][i] = -1;
} else {
go[C][0][i] = lose[i];
gain[C][0][i] = p[i];
lim[C][0][i] = s[i];
}
}
}
}
for (int C = 0; C < LS; C++) {
for (int j = 1; j < LN; j++) {
for (int i = 0; i < n; i++) {
if (go[C][j - 1][i] == -1 || go[C][j - 1][go[C][j - 1][i]] == -1) {
go[C][j][i] = -1;
continue;
}
go[C][j][i] = go[C][j - 1][go[C][j - 1][i]];
gain[C][j][i] = gain[C][j - 1][i] + gain[C][j - 1][go[C][j - 1][i]];
lim[C][j][i] = min(lim[C][j - 1][i], lim[C][j - 1][go[C][j - 1][i]] - gain[C][j - 1][i]);
}
}
}
}
long long simulate(int x, int z) {
long long str = z, c = 0;
while (x != n) {
while (c + 1 < LS && pw[c + 1] <= str) c++;
for (int i = LN - 1; i >= 0; i--) {
if (go[c][i][x] == -1) continue;
if (str < lim[c][i][x]) {
str += gain[c][i][x];
x = go[c][i][x];
}
}
if (str >= s[x]) str += s[x], x = win[x];
else str += p[x], x = lose[x];
}
return str;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2516 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
3 ms |
4820 KB |
Output is correct |
4 |
Correct |
70 ms |
104728 KB |
Output is correct |
5 |
Correct |
4 ms |
6740 KB |
Output is correct |
6 |
Correct |
69 ms |
104736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6100 KB |
Output is correct |
2 |
Correct |
724 ms |
1144164 KB |
Output is correct |
3 |
Correct |
668 ms |
1148364 KB |
Output is correct |
4 |
Correct |
678 ms |
1148356 KB |
Output is correct |
5 |
Correct |
723 ms |
1068868 KB |
Output is correct |
6 |
Correct |
759 ms |
1144200 KB |
Output is correct |
7 |
Correct |
833 ms |
1148360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5972 KB |
Output is correct |
2 |
Correct |
167 ms |
137572 KB |
Output is correct |
3 |
Correct |
141 ms |
144852 KB |
Output is correct |
4 |
Correct |
95 ms |
112756 KB |
Output is correct |
5 |
Correct |
88 ms |
109908 KB |
Output is correct |
6 |
Correct |
204 ms |
137552 KB |
Output is correct |
7 |
Correct |
155 ms |
137412 KB |
Output is correct |
8 |
Correct |
110 ms |
112484 KB |
Output is correct |
9 |
Correct |
105 ms |
73304 KB |
Output is correct |
10 |
Correct |
121 ms |
112484 KB |
Output is correct |
11 |
Correct |
116 ms |
104820 KB |
Output is correct |
12 |
Correct |
221 ms |
140764 KB |
Output is correct |
13 |
Correct |
151 ms |
133540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5972 KB |
Output is correct |
2 |
Correct |
167 ms |
137572 KB |
Output is correct |
3 |
Correct |
141 ms |
144852 KB |
Output is correct |
4 |
Correct |
95 ms |
112756 KB |
Output is correct |
5 |
Correct |
88 ms |
109908 KB |
Output is correct |
6 |
Correct |
204 ms |
137552 KB |
Output is correct |
7 |
Correct |
155 ms |
137412 KB |
Output is correct |
8 |
Correct |
110 ms |
112484 KB |
Output is correct |
9 |
Correct |
105 ms |
73304 KB |
Output is correct |
10 |
Correct |
121 ms |
112484 KB |
Output is correct |
11 |
Correct |
116 ms |
104820 KB |
Output is correct |
12 |
Correct |
221 ms |
140764 KB |
Output is correct |
13 |
Correct |
151 ms |
133540 KB |
Output is correct |
14 |
Correct |
3 ms |
6100 KB |
Output is correct |
15 |
Correct |
119 ms |
137524 KB |
Output is correct |
16 |
Correct |
170 ms |
137512 KB |
Output is correct |
17 |
Correct |
113 ms |
144472 KB |
Output is correct |
18 |
Correct |
113 ms |
144508 KB |
Output is correct |
19 |
Correct |
192 ms |
137552 KB |
Output is correct |
20 |
Correct |
189 ms |
144896 KB |
Output is correct |
21 |
Correct |
193 ms |
144780 KB |
Output is correct |
22 |
Correct |
145 ms |
98072 KB |
Output is correct |
23 |
Correct |
145 ms |
140792 KB |
Output is correct |
24 |
Correct |
291 ms |
140688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5972 KB |
Output is correct |
2 |
Correct |
167 ms |
137572 KB |
Output is correct |
3 |
Correct |
141 ms |
144852 KB |
Output is correct |
4 |
Correct |
95 ms |
112756 KB |
Output is correct |
5 |
Correct |
88 ms |
109908 KB |
Output is correct |
6 |
Correct |
204 ms |
137552 KB |
Output is correct |
7 |
Correct |
155 ms |
137412 KB |
Output is correct |
8 |
Correct |
110 ms |
112484 KB |
Output is correct |
9 |
Correct |
105 ms |
73304 KB |
Output is correct |
10 |
Correct |
121 ms |
112484 KB |
Output is correct |
11 |
Correct |
116 ms |
104820 KB |
Output is correct |
12 |
Correct |
221 ms |
140764 KB |
Output is correct |
13 |
Correct |
151 ms |
133540 KB |
Output is correct |
14 |
Correct |
3 ms |
6100 KB |
Output is correct |
15 |
Correct |
119 ms |
137524 KB |
Output is correct |
16 |
Correct |
170 ms |
137512 KB |
Output is correct |
17 |
Correct |
113 ms |
144472 KB |
Output is correct |
18 |
Correct |
113 ms |
144508 KB |
Output is correct |
19 |
Correct |
192 ms |
137552 KB |
Output is correct |
20 |
Correct |
189 ms |
144896 KB |
Output is correct |
21 |
Correct |
193 ms |
144780 KB |
Output is correct |
22 |
Correct |
145 ms |
98072 KB |
Output is correct |
23 |
Correct |
145 ms |
140792 KB |
Output is correct |
24 |
Correct |
291 ms |
140688 KB |
Output is correct |
25 |
Correct |
87 ms |
136716 KB |
Output is correct |
26 |
Correct |
155 ms |
137548 KB |
Output is correct |
27 |
Correct |
123 ms |
137424 KB |
Output is correct |
28 |
Correct |
123 ms |
137472 KB |
Output is correct |
29 |
Correct |
172 ms |
137516 KB |
Output is correct |
30 |
Correct |
166 ms |
145376 KB |
Output is correct |
31 |
Correct |
167 ms |
145356 KB |
Output is correct |
32 |
Correct |
296 ms |
140768 KB |
Output is correct |
33 |
Correct |
598 ms |
141152 KB |
Output is correct |
34 |
Correct |
1231 ms |
141612 KB |
Output is correct |
35 |
Correct |
607 ms |
133576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
6100 KB |
Output is correct |
2 |
Correct |
724 ms |
1144164 KB |
Output is correct |
3 |
Correct |
668 ms |
1148364 KB |
Output is correct |
4 |
Correct |
678 ms |
1148356 KB |
Output is correct |
5 |
Correct |
723 ms |
1068868 KB |
Output is correct |
6 |
Correct |
759 ms |
1144200 KB |
Output is correct |
7 |
Correct |
833 ms |
1148360 KB |
Output is correct |
8 |
Correct |
3 ms |
5972 KB |
Output is correct |
9 |
Correct |
167 ms |
137572 KB |
Output is correct |
10 |
Correct |
141 ms |
144852 KB |
Output is correct |
11 |
Correct |
95 ms |
112756 KB |
Output is correct |
12 |
Correct |
88 ms |
109908 KB |
Output is correct |
13 |
Correct |
204 ms |
137552 KB |
Output is correct |
14 |
Correct |
155 ms |
137412 KB |
Output is correct |
15 |
Correct |
110 ms |
112484 KB |
Output is correct |
16 |
Correct |
105 ms |
73304 KB |
Output is correct |
17 |
Correct |
121 ms |
112484 KB |
Output is correct |
18 |
Correct |
116 ms |
104820 KB |
Output is correct |
19 |
Correct |
221 ms |
140764 KB |
Output is correct |
20 |
Correct |
151 ms |
133540 KB |
Output is correct |
21 |
Correct |
3 ms |
6100 KB |
Output is correct |
22 |
Correct |
119 ms |
137524 KB |
Output is correct |
23 |
Correct |
170 ms |
137512 KB |
Output is correct |
24 |
Correct |
113 ms |
144472 KB |
Output is correct |
25 |
Correct |
113 ms |
144508 KB |
Output is correct |
26 |
Correct |
192 ms |
137552 KB |
Output is correct |
27 |
Correct |
189 ms |
144896 KB |
Output is correct |
28 |
Correct |
193 ms |
144780 KB |
Output is correct |
29 |
Correct |
145 ms |
98072 KB |
Output is correct |
30 |
Correct |
145 ms |
140792 KB |
Output is correct |
31 |
Correct |
291 ms |
140688 KB |
Output is correct |
32 |
Correct |
87 ms |
136716 KB |
Output is correct |
33 |
Correct |
155 ms |
137548 KB |
Output is correct |
34 |
Correct |
123 ms |
137424 KB |
Output is correct |
35 |
Correct |
123 ms |
137472 KB |
Output is correct |
36 |
Correct |
172 ms |
137516 KB |
Output is correct |
37 |
Correct |
166 ms |
145376 KB |
Output is correct |
38 |
Correct |
167 ms |
145356 KB |
Output is correct |
39 |
Correct |
296 ms |
140768 KB |
Output is correct |
40 |
Correct |
598 ms |
141152 KB |
Output is correct |
41 |
Correct |
1231 ms |
141612 KB |
Output is correct |
42 |
Correct |
607 ms |
133576 KB |
Output is correct |
43 |
Correct |
1 ms |
1748 KB |
Output is correct |
44 |
Correct |
4 ms |
6100 KB |
Output is correct |
45 |
Correct |
872 ms |
1068744 KB |
Output is correct |
46 |
Correct |
738 ms |
1068588 KB |
Output is correct |
47 |
Correct |
738 ms |
1068748 KB |
Output is correct |
48 |
Correct |
759 ms |
1144228 KB |
Output is correct |
49 |
Correct |
896 ms |
1068888 KB |
Output is correct |
50 |
Correct |
720 ms |
1144256 KB |
Output is correct |
51 |
Correct |
680 ms |
1142092 KB |
Output is correct |
52 |
Correct |
715 ms |
1144268 KB |
Output is correct |
53 |
Correct |
1275 ms |
1106224 KB |
Output is correct |
54 |
Correct |
2045 ms |
1116528 KB |
Output is correct |
55 |
Correct |
2314 ms |
1119244 KB |
Output is correct |
56 |
Correct |
1690 ms |
1074728 KB |
Output is correct |
57 |
Correct |
2021 ms |
1068740 KB |
Output is correct |
58 |
Correct |
2178 ms |
1068816 KB |
Output is correct |
59 |
Correct |
2277 ms |
1068772 KB |
Output is correct |
60 |
Correct |
2036 ms |
1136708 KB |
Output is correct |
61 |
Correct |
1926 ms |
1118792 KB |
Output is correct |