oj.uz

Submission #921297

# Submission time Handle Problem Language Result Execution time Memory
921297 2024-02-03T16:37:51 Z byunjaewoo Dungeons Game (IOI21_dungeons) C++17
63 / 100
 4588 ms 2097152 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using ll=long long;
 
const int Nmax=400001;
int N, S[Nmax], P[Nmax], W[Nmax], L[Nmax];
ll DP[Nmax];
std::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=0; i<24; i++) for(int j=0; j<=N; j++) nxt[i][j].resize(i), mx[i][j].resize(i), sum[i][j].resize(i);
	for(int i=1; i<24; i++) {
		for(int j=0; j<N; j++) {
			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][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][j]=nxt[i][nxt[i][k][j-1]][j-1];
			sum[i][k][j]=std::min(sum[i][k][j-1]+sum[i][nxt[i][k][j-1]][j-1], 1000000000);
			mx[i][k][j]=std::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

# Verdict Execution time Memory Grader output
1 Correct 189 ms 683856 KB Output is correct
2 Correct 163 ms 683856 KB Output is correct
3 Correct 178 ms 692564 KB Output is correct
4 Correct 701 ms 900436 KB Output is correct
5 Correct 174 ms 692564 KB Output is correct
6 Correct 667 ms 899924 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 688268 KB Output is correct
2 Runtime error 1443 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 688072 KB Output is correct
2 Correct 961 ms 901652 KB Output is correct
3 Correct 931 ms 901684 KB Output is correct
4 Correct 969 ms 900196 KB Output is correct
5 Correct 942 ms 899972 KB Output is correct
6 Correct 981 ms 899928 KB Output is correct
7 Correct 1042 ms 900176 KB Output is correct
8 Correct 1465 ms 900292 KB Output is correct
9 Correct 845 ms 899976 KB Output is correct
10 Correct 1407 ms 899724 KB Output is correct
11 Correct 1771 ms 899924 KB Output is correct
12 Correct 4588 ms 899920 KB Output is correct
13 Correct 4336 ms 899972 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 688072 KB Output is correct
2 Correct 961 ms 901652 KB Output is correct
3 Correct 931 ms 901684 KB Output is correct
4 Correct 969 ms 900196 KB Output is correct
5 Correct 942 ms 899972 KB Output is correct
6 Correct 981 ms 899928 KB Output is correct
7 Correct 1042 ms 900176 KB Output is correct
8 Correct 1465 ms 900292 KB Output is correct
9 Correct 845 ms 899976 KB Output is correct
10 Correct 1407 ms 899724 KB Output is correct
11 Correct 1771 ms 899924 KB Output is correct
12 Correct 4588 ms 899920 KB Output is correct
13 Correct 4336 ms 899972 KB Output is correct
14 Correct 170 ms 688236 KB Output is correct
15 Correct 927 ms 900176 KB Output is correct
16 Correct 971 ms 900036 KB Output is correct
17 Correct 1209 ms 899924 KB Output is correct
18 Correct 1135 ms 900180 KB Output is correct
19 Correct 1008 ms 900008 KB Output is correct
20 Correct 1131 ms 899760 KB Output is correct
21 Correct 1365 ms 899764 KB Output is correct
22 Correct 1430 ms 899948 KB Output is correct
23 Correct 2326 ms 899816 KB Output is correct
24 Correct 2506 ms 899920 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 688072 KB Output is correct
2 Correct 961 ms 901652 KB Output is correct
3 Correct 931 ms 901684 KB Output is correct
4 Correct 969 ms 900196 KB Output is correct
5 Correct 942 ms 899972 KB Output is correct
6 Correct 981 ms 899928 KB Output is correct
7 Correct 1042 ms 900176 KB Output is correct
8 Correct 1465 ms 900292 KB Output is correct
9 Correct 845 ms 899976 KB Output is correct
10 Correct 1407 ms 899724 KB Output is correct
11 Correct 1771 ms 899924 KB Output is correct
12 Correct 4588 ms 899920 KB Output is correct
13 Correct 4336 ms 899972 KB Output is correct
14 Correct 170 ms 688236 KB Output is correct
15 Correct 927 ms 900176 KB Output is correct
16 Correct 971 ms 900036 KB Output is correct
17 Correct 1209 ms 899924 KB Output is correct
18 Correct 1135 ms 900180 KB Output is correct
19 Correct 1008 ms 900008 KB Output is correct
20 Correct 1131 ms 899760 KB Output is correct
21 Correct 1365 ms 899764 KB Output is correct
22 Correct 1430 ms 899948 KB Output is correct
23 Correct 2326 ms 899816 KB Output is correct
24 Correct 2506 ms 899920 KB Output is correct
25 Correct 709 ms 899212 KB Output is correct
26 Correct 1083 ms 900152 KB Output is correct
27 Correct 1025 ms 899980 KB Output is correct
28 Correct 951 ms 899972 KB Output is correct
29 Correct 981 ms 899792 KB Output is correct
30 Correct 1204 ms 899996 KB Output is correct
31 Correct 1392 ms 899972 KB Output is correct
32 Correct 1550 ms 899972 KB Output is correct
33 Correct 1024 ms 899892 KB Output is correct
34 Correct 1874 ms 899764 KB Output is correct
35 Correct 1196 ms 899976 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 688268 KB Output is correct
2 Runtime error 1443 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -