oj.uz

답안 #437969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437969 2021-06-27T11:10:14 Z gs14004 던전 (IOI21_dungeons) C++17
100 / 100
 5370 ms 971604 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXN = 400005;

int n;
vector<int> s, p, w, l;
int nxt[8][25][MAXN];
int cost[8][25][MAXN];
int value[8][25][MAXN];
lint dp[MAXN];

void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
	tie(n, s, p, w, l) = make_tuple(_n, _s, _p, _w, _l);
	s.resize(n + 1);
	for(int i = n - 1; i >= 0; i--) dp[i] = dp[w[i]] + s[i];
	for(int i = 0; i < 8; i++){
		int L = (1 << (3*i));
		for(int j = 0; j < n; j++){
			if(s[j] < L){
				nxt[i][0][j] = w[j];
				cost[i][0][j] = s[j];
				value[i][0][j] = 1e9;
			}
			else{
				nxt[i][0][j] = l[j];
				cost[i][0][j] = p[j];
				value[i][0][j] = s[j];
			}
		}
		nxt[i][0][n] = n;
		cost[i][0][n] = 1e8;
		value[i][0][n] = 1e9;
		for(int j = 1; j < 25; j++){
			for(int k = 0; k <= n; k++){
				nxt[i][j][k] = nxt[i][j-1][nxt[i][j-1][k]];
				cost[i][j][k] = cost[i][j-1][k] + cost[i][j-1][nxt[i][j-1][k]];
				cost[i][j][k] = min(cost[i][j][k], int(1e9));
				value[i][j][k] = min(value[i][j-1][k], value[i][j-1][nxt[i][j-1][k]] - cost[i][j-1][k]);
				value[i][j][k] = max(value[i][j][k], 0);
			}
		}
	}
	return;
}

long long simulate(int x, int zz) {
	lint z = zz;
	for(int i = 0; i < 8; i++){
		while(z < (1 << (3*i+3))){
			for(int j = 24; j >= 0; j--){
				if(nxt[i][j][x] != n && z + cost[i][j][x] < (1<<(3*i+3)) && value[i][j][x] > z){
					z += cost[i][j][x];
					x = nxt[i][j][x];
				}
			}
			if(x != n && z < (1 << (3*i+3)) && (s[x] > z || s[x] < (1 << (2*i)))){
				z += cost[i][0][x];
				x = nxt[i][0][x];
			}
			if(x == n){
				break;
			}
			if(s[x] <= z){
				z += s[x];
				x = w[x];
			}
			if(x == n) break;
		}
	}
	return z + dp[x];
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4428 KB Output is correct
2 Correct 4 ms 4556 KB Output is correct
3 Correct 9 ms 9292 KB Output is correct
4 Correct 133 ms 124664 KB Output is correct
5 Correct 9 ms 9276 KB Output is correct
6 Correct 146 ms 124672 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6988 KB Output is correct
2 Correct 1110 ms 962560 KB Output is correct
3 Correct 1201 ms 964888 KB Output is correct
4 Correct 1250 ms 965048 KB Output is correct
5 Correct 1349 ms 964680 KB Output is correct
6 Correct 2219 ms 965808 KB Output is correct
7 Correct 1803 ms 964680 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6860 KB Output is correct
2 Correct 281 ms 125168 KB Output is correct
3 Correct 255 ms 125184 KB Output is correct
4 Correct 173 ms 125140 KB Output is correct
5 Correct 179 ms 125196 KB Output is correct
6 Correct 700 ms 125184 KB Output is correct
7 Correct 613 ms 125184 KB Output is correct
8 Correct 443 ms 125184 KB Output is correct
9 Correct 235 ms 125192 KB Output is correct
10 Correct 379 ms 125184 KB Output is correct
11 Correct 538 ms 125312 KB Output is correct
12 Correct 1103 ms 125192 KB Output is correct
13 Correct 1118 ms 125312 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6860 KB Output is correct
2 Correct 281 ms 125168 KB Output is correct
3 Correct 255 ms 125184 KB Output is correct
4 Correct 173 ms 125140 KB Output is correct
5 Correct 179 ms 125196 KB Output is correct
6 Correct 700 ms 125184 KB Output is correct
7 Correct 613 ms 125184 KB Output is correct
8 Correct 443 ms 125184 KB Output is correct
9 Correct 235 ms 125192 KB Output is correct
10 Correct 379 ms 125184 KB Output is correct
11 Correct 538 ms 125312 KB Output is correct
12 Correct 1103 ms 125192 KB Output is correct
13 Correct 1118 ms 125312 KB Output is correct
14 Correct 6 ms 6860 KB Output is correct
15 Correct 201 ms 125144 KB Output is correct
16 Correct 265 ms 125180 KB Output is correct
17 Correct 227 ms 125184 KB Output is correct
18 Correct 224 ms 125184 KB Output is correct
19 Correct 598 ms 125200 KB Output is correct
20 Correct 437 ms 125180 KB Output is correct
21 Correct 495 ms 125200 KB Output is correct
22 Correct 585 ms 125148 KB Output is correct
23 Correct 785 ms 125140 KB Output is correct
24 Correct 793 ms 125184 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6860 KB Output is correct
2 Correct 281 ms 125168 KB Output is correct
3 Correct 255 ms 125184 KB Output is correct
4 Correct 173 ms 125140 KB Output is correct
5 Correct 179 ms 125196 KB Output is correct
6 Correct 700 ms 125184 KB Output is correct
7 Correct 613 ms 125184 KB Output is correct
8 Correct 443 ms 125184 KB Output is correct
9 Correct 235 ms 125192 KB Output is correct
10 Correct 379 ms 125184 KB Output is correct
11 Correct 538 ms 125312 KB Output is correct
12 Correct 1103 ms 125192 KB Output is correct
13 Correct 1118 ms 125312 KB Output is correct
14 Correct 6 ms 6860 KB Output is correct
15 Correct 201 ms 125144 KB Output is correct
16 Correct 265 ms 125180 KB Output is correct
17 Correct 227 ms 125184 KB Output is correct
18 Correct 224 ms 125184 KB Output is correct
19 Correct 598 ms 125200 KB Output is correct
20 Correct 437 ms 125180 KB Output is correct
21 Correct 495 ms 125200 KB Output is correct
22 Correct 585 ms 125148 KB Output is correct
23 Correct 785 ms 125140 KB Output is correct
24 Correct 793 ms 125184 KB Output is correct
25 Correct 137 ms 124464 KB Output is correct
26 Correct 261 ms 125172 KB Output is correct
27 Correct 206 ms 125184 KB Output is correct
28 Correct 218 ms 125192 KB Output is correct
29 Correct 334 ms 125188 KB Output is correct
30 Correct 425 ms 125220 KB Output is correct
31 Correct 620 ms 125284 KB Output is correct
32 Correct 747 ms 125184 KB Output is correct
33 Correct 1632 ms 125196 KB Output is correct
34 Correct 2300 ms 125188 KB Output is correct
35 Correct 1437 ms 125312 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6988 KB Output is correct
2 Correct 1110 ms 962560 KB Output is correct
3 Correct 1201 ms 964888 KB Output is correct
4 Correct 1250 ms 965048 KB Output is correct
5 Correct 1349 ms 964680 KB Output is correct
6 Correct 2219 ms 965808 KB Output is correct
7 Correct 1803 ms 964680 KB Output is correct
8 Correct 6 ms 6860 KB Output is correct
9 Correct 281 ms 125168 KB Output is correct
10 Correct 255 ms 125184 KB Output is correct
11 Correct 173 ms 125140 KB Output is correct
12 Correct 179 ms 125196 KB Output is correct
13 Correct 700 ms 125184 KB Output is correct
14 Correct 613 ms 125184 KB Output is correct
15 Correct 443 ms 125184 KB Output is correct
16 Correct 235 ms 125192 KB Output is correct
17 Correct 379 ms 125184 KB Output is correct
18 Correct 538 ms 125312 KB Output is correct
19 Correct 1103 ms 125192 KB Output is correct
20 Correct 1118 ms 125312 KB Output is correct
21 Correct 6 ms 6860 KB Output is correct
22 Correct 201 ms 125144 KB Output is correct
23 Correct 265 ms 125180 KB Output is correct
24 Correct 227 ms 125184 KB Output is correct
25 Correct 224 ms 125184 KB Output is correct
26 Correct 598 ms 125200 KB Output is correct
27 Correct 437 ms 125180 KB Output is correct
28 Correct 495 ms 125200 KB Output is correct
29 Correct 585 ms 125148 KB Output is correct
30 Correct 785 ms 125140 KB Output is correct
31 Correct 793 ms 125184 KB Output is correct
32 Correct 137 ms 124464 KB Output is correct
33 Correct 261 ms 125172 KB Output is correct
34 Correct 206 ms 125184 KB Output is correct
35 Correct 218 ms 125192 KB Output is correct
36 Correct 334 ms 125188 KB Output is correct
37 Correct 425 ms 125220 KB Output is correct
38 Correct 620 ms 125284 KB Output is correct
39 Correct 747 ms 125184 KB Output is correct
40 Correct 1632 ms 125196 KB Output is correct
41 Correct 2300 ms 125188 KB Output is correct
42 Correct 1437 ms 125312 KB Output is correct
43 Correct 3 ms 4428 KB Output is correct
44 Correct 6 ms 6988 KB Output is correct
45 Correct 1603 ms 966100 KB Output is correct
46 Correct 1101 ms 965580 KB Output is correct
47 Correct 1203 ms 965240 KB Output is correct
48 Correct 1164 ms 966240 KB Output is correct
49 Correct 1705 ms 966296 KB Output is correct
50 Correct 1498 ms 966832 KB Output is correct
51 Correct 1180 ms 966236 KB Output is correct
52 Correct 1575 ms 965160 KB Output is correct
53 Correct 3007 ms 965916 KB Output is correct
54 Correct 3364 ms 971604 KB Output is correct
55 Correct 4141 ms 970072 KB Output is correct
56 Correct 3567 ms 971008 KB Output is correct
57 Correct 5370 ms 970592 KB Output is correct
58 Correct 4066 ms 971144 KB Output is correct
59 Correct 4461 ms 970812 KB Output is correct
60 Correct 2808 ms 970632 KB Output is correct
61 Correct 2605 ms 970072 KB Output is correct