#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 400050;
const int L = 24;
const int K = 8;
const ll inf = (ll)1e18;
int n, nxt[K][L][N], S[N], W[N];
ll pw[K + 5], sum[K][L][N], mn[K][L][N], ft[N];
vector<pair<int, int>> E[N];
void DFS(int u, ll tot) {
ft[u] = tot;
for (auto e : E[u])
DFS(e.first, tot + e.second);
}
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
::n = n;
for (int i = 0; i < n; i++)
S[i] = s[i], W[i] = w[i];
W[n] = n;
S[n] = 0;
pw[0] = 1;
for (int i = 1; i <= K; i++)
pw[i] = pw[i - 1] * 8;
for (int i = 0; i < K; i++) {
int h = pw[i];
nxt[i][0][n] = n;
sum[i][0][n] = 0;
mn[i][0][n] = inf;
for (int j = 0; j < n; j++) {
if (s[j] <= h) {
nxt[i][0][j] = w[j];
sum[i][0][j] = s[j];
mn[i][0][j] = inf;
} else {
nxt[i][0][j] = l[j];
sum[i][0][j] = p[j];
mn[i][0][j] = s[j];
}
}
for (int j = 1; j < L; j++)
for (int l = 0; l <= n; l++) {
nxt[i][j][l] = nxt[i][j - 1][nxt[i][j - 1][l]];
sum[i][j][l] = min(inf, sum[i][j - 1][l] + sum[i][j - 1][nxt[i][j - 1][l]]);
mn[i][j][l] = min(mn[i][j - 1][l], mn[i][j - 1][nxt[i][j - 1][l]] - sum[i][j - 1][l]);
}
}
for (int i = 0; i < n; i++)
E[w[i]].push_back({i, s[i]});
DFS(n, 0);
}
ll simulate(int x, int z) {
ll h = z;
for (int i = 0; i < K; i++) {
while (1) {
if (h >= pw[i + 1] || x == n)
break;
for (int j = L - 1; j >= 0; j--) {
if (mn[i][j][x] > h) {
h += sum[i][j][x];
x = nxt[i][j][x];
}
}
h += S[x];
x = W[x];
}
}
return h + ft[x];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
136 ms |
650832 KB |
Output is correct |
2 |
Correct |
68 ms |
650832 KB |
Output is correct |
3 |
Correct |
68 ms |
654160 KB |
Output is correct |
4 |
Correct |
137 ms |
728816 KB |
Output is correct |
5 |
Correct |
74 ms |
635728 KB |
Output is correct |
6 |
Correct |
137 ms |
726668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
632148 KB |
Output is correct |
2 |
Correct |
990 ms |
1548864 KB |
Output is correct |
3 |
Correct |
813 ms |
1555308 KB |
Output is correct |
4 |
Correct |
828 ms |
1557932 KB |
Output is correct |
5 |
Correct |
977 ms |
1544924 KB |
Output is correct |
6 |
Correct |
928 ms |
1552084 KB |
Output is correct |
7 |
Correct |
875 ms |
1557484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
660668 KB |
Output is correct |
2 |
Correct |
214 ms |
750608 KB |
Output is correct |
3 |
Correct |
190 ms |
751628 KB |
Output is correct |
4 |
Correct |
162 ms |
754248 KB |
Output is correct |
5 |
Correct |
165 ms |
750004 KB |
Output is correct |
6 |
Correct |
230 ms |
752376 KB |
Output is correct |
7 |
Correct |
218 ms |
750676 KB |
Output is correct |
8 |
Correct |
165 ms |
754324 KB |
Output is correct |
9 |
Correct |
171 ms |
752388 KB |
Output is correct |
10 |
Correct |
165 ms |
752364 KB |
Output is correct |
11 |
Correct |
168 ms |
752512 KB |
Output is correct |
12 |
Correct |
248 ms |
749036 KB |
Output is correct |
13 |
Correct |
205 ms |
752080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
660668 KB |
Output is correct |
2 |
Correct |
214 ms |
750608 KB |
Output is correct |
3 |
Correct |
190 ms |
751628 KB |
Output is correct |
4 |
Correct |
162 ms |
754248 KB |
Output is correct |
5 |
Correct |
165 ms |
750004 KB |
Output is correct |
6 |
Correct |
230 ms |
752376 KB |
Output is correct |
7 |
Correct |
218 ms |
750676 KB |
Output is correct |
8 |
Correct |
165 ms |
754324 KB |
Output is correct |
9 |
Correct |
171 ms |
752388 KB |
Output is correct |
10 |
Correct |
165 ms |
752364 KB |
Output is correct |
11 |
Correct |
168 ms |
752512 KB |
Output is correct |
12 |
Correct |
248 ms |
749036 KB |
Output is correct |
13 |
Correct |
205 ms |
752080 KB |
Output is correct |
14 |
Correct |
67 ms |
662608 KB |
Output is correct |
15 |
Correct |
173 ms |
750448 KB |
Output is correct |
16 |
Correct |
187 ms |
752368 KB |
Output is correct |
17 |
Correct |
164 ms |
751444 KB |
Output is correct |
18 |
Correct |
168 ms |
751484 KB |
Output is correct |
19 |
Correct |
205 ms |
750580 KB |
Output is correct |
20 |
Correct |
191 ms |
753968 KB |
Output is correct |
21 |
Correct |
190 ms |
751548 KB |
Output is correct |
22 |
Correct |
161 ms |
752980 KB |
Output is correct |
23 |
Correct |
178 ms |
750756 KB |
Output is correct |
24 |
Correct |
286 ms |
750596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
660668 KB |
Output is correct |
2 |
Correct |
214 ms |
750608 KB |
Output is correct |
3 |
Correct |
190 ms |
751628 KB |
Output is correct |
4 |
Correct |
162 ms |
754248 KB |
Output is correct |
5 |
Correct |
165 ms |
750004 KB |
Output is correct |
6 |
Correct |
230 ms |
752376 KB |
Output is correct |
7 |
Correct |
218 ms |
750676 KB |
Output is correct |
8 |
Correct |
165 ms |
754324 KB |
Output is correct |
9 |
Correct |
171 ms |
752388 KB |
Output is correct |
10 |
Correct |
165 ms |
752364 KB |
Output is correct |
11 |
Correct |
168 ms |
752512 KB |
Output is correct |
12 |
Correct |
248 ms |
749036 KB |
Output is correct |
13 |
Correct |
205 ms |
752080 KB |
Output is correct |
14 |
Correct |
67 ms |
662608 KB |
Output is correct |
15 |
Correct |
173 ms |
750448 KB |
Output is correct |
16 |
Correct |
187 ms |
752368 KB |
Output is correct |
17 |
Correct |
164 ms |
751444 KB |
Output is correct |
18 |
Correct |
168 ms |
751484 KB |
Output is correct |
19 |
Correct |
205 ms |
750580 KB |
Output is correct |
20 |
Correct |
191 ms |
753968 KB |
Output is correct |
21 |
Correct |
190 ms |
751548 KB |
Output is correct |
22 |
Correct |
161 ms |
752980 KB |
Output is correct |
23 |
Correct |
178 ms |
750756 KB |
Output is correct |
24 |
Correct |
286 ms |
750596 KB |
Output is correct |
25 |
Correct |
146 ms |
749904 KB |
Output is correct |
26 |
Correct |
193 ms |
748988 KB |
Output is correct |
27 |
Correct |
170 ms |
754168 KB |
Output is correct |
28 |
Correct |
169 ms |
750576 KB |
Output is correct |
29 |
Correct |
201 ms |
750512 KB |
Output is correct |
30 |
Correct |
200 ms |
754256 KB |
Output is correct |
31 |
Correct |
202 ms |
752392 KB |
Output is correct |
32 |
Correct |
316 ms |
745604 KB |
Output is correct |
33 |
Correct |
413 ms |
749392 KB |
Output is correct |
34 |
Correct |
1115 ms |
746136 KB |
Output is correct |
35 |
Correct |
357 ms |
750844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
632148 KB |
Output is correct |
2 |
Correct |
990 ms |
1548864 KB |
Output is correct |
3 |
Correct |
813 ms |
1555308 KB |
Output is correct |
4 |
Correct |
828 ms |
1557932 KB |
Output is correct |
5 |
Correct |
977 ms |
1544924 KB |
Output is correct |
6 |
Correct |
928 ms |
1552084 KB |
Output is correct |
7 |
Correct |
875 ms |
1557484 KB |
Output is correct |
8 |
Correct |
70 ms |
660668 KB |
Output is correct |
9 |
Correct |
214 ms |
750608 KB |
Output is correct |
10 |
Correct |
190 ms |
751628 KB |
Output is correct |
11 |
Correct |
162 ms |
754248 KB |
Output is correct |
12 |
Correct |
165 ms |
750004 KB |
Output is correct |
13 |
Correct |
230 ms |
752376 KB |
Output is correct |
14 |
Correct |
218 ms |
750676 KB |
Output is correct |
15 |
Correct |
165 ms |
754324 KB |
Output is correct |
16 |
Correct |
171 ms |
752388 KB |
Output is correct |
17 |
Correct |
165 ms |
752364 KB |
Output is correct |
18 |
Correct |
168 ms |
752512 KB |
Output is correct |
19 |
Correct |
248 ms |
749036 KB |
Output is correct |
20 |
Correct |
205 ms |
752080 KB |
Output is correct |
21 |
Correct |
67 ms |
662608 KB |
Output is correct |
22 |
Correct |
173 ms |
750448 KB |
Output is correct |
23 |
Correct |
187 ms |
752368 KB |
Output is correct |
24 |
Correct |
164 ms |
751444 KB |
Output is correct |
25 |
Correct |
168 ms |
751484 KB |
Output is correct |
26 |
Correct |
205 ms |
750580 KB |
Output is correct |
27 |
Correct |
191 ms |
753968 KB |
Output is correct |
28 |
Correct |
190 ms |
751548 KB |
Output is correct |
29 |
Correct |
161 ms |
752980 KB |
Output is correct |
30 |
Correct |
178 ms |
750756 KB |
Output is correct |
31 |
Correct |
286 ms |
750596 KB |
Output is correct |
32 |
Correct |
146 ms |
749904 KB |
Output is correct |
33 |
Correct |
193 ms |
748988 KB |
Output is correct |
34 |
Correct |
170 ms |
754168 KB |
Output is correct |
35 |
Correct |
169 ms |
750576 KB |
Output is correct |
36 |
Correct |
201 ms |
750512 KB |
Output is correct |
37 |
Correct |
200 ms |
754256 KB |
Output is correct |
38 |
Correct |
202 ms |
752392 KB |
Output is correct |
39 |
Correct |
316 ms |
745604 KB |
Output is correct |
40 |
Correct |
413 ms |
749392 KB |
Output is correct |
41 |
Correct |
1115 ms |
746136 KB |
Output is correct |
42 |
Correct |
357 ms |
750844 KB |
Output is correct |
43 |
Correct |
65 ms |
661028 KB |
Output is correct |
44 |
Correct |
65 ms |
660620 KB |
Output is correct |
45 |
Correct |
1070 ms |
1551952 KB |
Output is correct |
46 |
Correct |
844 ms |
1546912 KB |
Output is correct |
47 |
Correct |
855 ms |
1547292 KB |
Output is correct |
48 |
Correct |
826 ms |
1557376 KB |
Output is correct |
49 |
Correct |
1153 ms |
1551540 KB |
Output is correct |
50 |
Correct |
826 ms |
1556880 KB |
Output is correct |
51 |
Correct |
828 ms |
1555768 KB |
Output is correct |
52 |
Correct |
859 ms |
1554992 KB |
Output is correct |
53 |
Correct |
1823 ms |
1548820 KB |
Output is correct |
54 |
Correct |
1515 ms |
1553860 KB |
Output is correct |
55 |
Correct |
2145 ms |
1552952 KB |
Output is correct |
56 |
Correct |
1758 ms |
1549260 KB |
Output is correct |
57 |
Correct |
2308 ms |
1549572 KB |
Output is correct |
58 |
Correct |
1820 ms |
1549344 KB |
Output is correct |
59 |
Correct |
1877 ms |
1549464 KB |
Output is correct |
60 |
Correct |
1527 ms |
1552452 KB |
Output is correct |
61 |
Correct |
1467 ms |
1552740 KB |
Output is correct |