oj.uz

답안 #921300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
921300 2024-02-03T16:41:55 Z byunjaewoo 던전 (IOI21_dungeons) C++17
63 / 100
 4868 ms 2097152 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
 
const int Nmax=400001;
int N, S[Nmax], P[Nmax], W[Nmax], L[Nmax];
ll DP[Nmax];
vector<int> nxt[24][Nmax], mx[24][Nmax], sum[24][Nmax];
 
void init(int n, std::vector<int> S_, std::vector<int> P_, std::vector<int> W_, std::vector<int> L_) {
	N=n;
	for(int i=0; i<N; i++) S[i]=S_[i], P[i]=P_[i], W[i]=W_[i], L[i]=L_[i];
	for(int i=1; i<24; i++) {
		for(int j=0; j<N; j++) {
			nxt[i][j].emplace_back(0); sum[i][j].emplace_back(0); mx[i][j].emplace_back(0);
			if(S[j]>=(1<<(i+1))) nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=(1<<(i+1))-1-P[j];
			else if(S[j]<=(1<<i)) nxt[i][j][0]=W[j], sum[i][j][0]=S[j], mx[i][j][0]=(1<<(i+1))-1-S[j];
			else nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=std::min(S[j]-1, (1<<(i+1))-1-P[j]);
		}
		nxt[i][N].emplace_back(0); sum[i][N].emplace_back(0); mx[i][N].emplace_back(0);
		nxt[i][N][0]=N, sum[i][N][0]=0, mx[i][N][0]=(1<<(i+1))-1;
		for(int j=1; j<i; j++) for(int k=0; k<=N; k++) {
			nxt[i][k].emplace_back(0); sum[i][k].emplace_back(0); mx[i][k].emplace_back(0);
			nxt[i][k][j]=nxt[i][nxt[i][k][j-1]][j-1];
			sum[i][k][j]=min(sum[i][k][j-1]+sum[i][nxt[i][k][j-1]][j-1], 1000000000);
			mx[i][k][j]=min(mx[i][k][j-1], mx[i][nxt[i][k][j-1]][j-1]-sum[i][k][j-1]);
		}
	}
	for(int i=N-1; i>=0; i--) DP[i]=DP[W[i]]+S[i];
}

long long simulate(int x, int z) {
	int k=x; ll v=z;
	for(int i=0; i<24; i++) {
		int kk=k; ll vv=v;
		for(int j=i-1; j>=0; j--) if(vv<=mx[i][kk][j]) {
			vv+=sum[i][kk][j], kk=nxt[i][kk][j];
			if(kk==N) break;
		}
		if(kk==N) {
			for(int j=i-1; j>=0; j--) if(nxt[i][k][j]!=N) v+=sum[i][k][j], k=nxt[i][k][j];
			if(k!=N) v+=sum[i][k][0], k=nxt[i][k][0];
			return v;
		}
		if(vv<(1<<(i+1))) {
			if(vv>=S[kk]) vv+=S[kk], kk=W[kk];
			else vv+=P[kk], kk=L[kk];
		}
		k=kk, v=vv;
	}
	return v+DP[k];
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 683752 KB Output is correct
2 Correct 166 ms 683948 KB Output is correct
3 Correct 201 ms 695404 KB Output is correct
4 Correct 1093 ms 975388 KB Output is correct
5 Correct 198 ms 695632 KB Output is correct
6 Correct 1083 ms 975136 KB Output is correct

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 690000 KB Output is correct
2 Runtime error 4372 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 689676 KB Output is correct
2 Correct 1400 ms 976372 KB Output is correct
3 Correct 1307 ms 976384 KB Output is correct
4 Correct 1287 ms 975116 KB Output is correct
5 Correct 1328 ms 974980 KB Output is correct
6 Correct 1387 ms 975012 KB Output is correct
7 Correct 1429 ms 975112 KB Output is correct
8 Correct 1846 ms 974932 KB Output is correct
9 Correct 1195 ms 975192 KB Output is correct
10 Correct 1761 ms 975180 KB Output is correct
11 Correct 2231 ms 975044 KB Output is correct
12 Correct 4868 ms 975564 KB Output is correct
13 Correct 4806 ms 974960 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 689676 KB Output is correct
2 Correct 1400 ms 976372 KB Output is correct
3 Correct 1307 ms 976384 KB Output is correct
4 Correct 1287 ms 975116 KB Output is correct
5 Correct 1328 ms 974980 KB Output is correct
6 Correct 1387 ms 975012 KB Output is correct
7 Correct 1429 ms 975112 KB Output is correct
8 Correct 1846 ms 974932 KB Output is correct
9 Correct 1195 ms 975192 KB Output is correct
10 Correct 1761 ms 975180 KB Output is correct
11 Correct 2231 ms 975044 KB Output is correct
12 Correct 4868 ms 975564 KB Output is correct
13 Correct 4806 ms 974960 KB Output is correct
14 Correct 183 ms 689788 KB Output is correct
15 Correct 1322 ms 974956 KB Output is correct
16 Correct 1405 ms 975048 KB Output is correct
17 Correct 1456 ms 975204 KB Output is correct
18 Correct 1500 ms 975104 KB Output is correct
19 Correct 1413 ms 975208 KB Output is correct
20 Correct 1508 ms 975196 KB Output is correct
21 Correct 1741 ms 975280 KB Output is correct
22 Correct 1732 ms 975440 KB Output is correct
23 Correct 2827 ms 975176 KB Output is correct
24 Correct 2962 ms 975168 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 689676 KB Output is correct
2 Correct 1400 ms 976372 KB Output is correct
3 Correct 1307 ms 976384 KB Output is correct
4 Correct 1287 ms 975116 KB Output is correct
5 Correct 1328 ms 974980 KB Output is correct
6 Correct 1387 ms 975012 KB Output is correct
7 Correct 1429 ms 975112 KB Output is correct
8 Correct 1846 ms 974932 KB Output is correct
9 Correct 1195 ms 975192 KB Output is correct
10 Correct 1761 ms 975180 KB Output is correct
11 Correct 2231 ms 975044 KB Output is correct
12 Correct 4868 ms 975564 KB Output is correct
13 Correct 4806 ms 974960 KB Output is correct
14 Correct 183 ms 689788 KB Output is correct
15 Correct 1322 ms 974956 KB Output is correct
16 Correct 1405 ms 975048 KB Output is correct
17 Correct 1456 ms 975204 KB Output is correct
18 Correct 1500 ms 975104 KB Output is correct
19 Correct 1413 ms 975208 KB Output is correct
20 Correct 1508 ms 975196 KB Output is correct
21 Correct 1741 ms 975280 KB Output is correct
22 Correct 1732 ms 975440 KB Output is correct
23 Correct 2827 ms 975176 KB Output is correct
24 Correct 2962 ms 975168 KB Output is correct
25 Correct 1122 ms 974164 KB Output is correct
26 Correct 1383 ms 975444 KB Output is correct
27 Correct 1331 ms 975056 KB Output is correct
28 Correct 1311 ms 975136 KB Output is correct
29 Correct 1378 ms 975256 KB Output is correct
30 Correct 1640 ms 975116 KB Output is correct
31 Correct 1799 ms 975100 KB Output is correct
32 Correct 1986 ms 975116 KB Output is correct
33 Correct 1320 ms 975024 KB Output is correct
34 Correct 2021 ms 974948 KB Output is correct
35 Correct 1558 ms 974968 KB Output is correct

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 690000 KB Output is correct
2 Runtime error 4372 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -