oj.uz

Submission #921219

# Submission time Handle Problem Language Result Execution time Memory
921219 2024-02-03T14:44:22 Z byunjaewoo Dungeons Game (IOI21_dungeons) C++17
0 / 100
 49 ms 306004 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int Nmax=50010;
int N;
ll nxt[25][25][Nmax], sum[25][25][Nmax], mx[25][25][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<25; i++) {
		for(int j=0; j<N; j++) {
			if(S[j]>=(1<<(i+1))) nxt[i][0][j]=L[j], sum[i][0][j]=P[j], mx[i][0][j]=(1<<(i+1))-1;
			else if(S[j]<=(1<<i)) nxt[i][0][j]=W[j], sum[i][0][j]=S[j], mx[i][0][j]=(1<<(i+1))-1;
			else nxt[i][0][j]=L[j], sum[i][0][j]=P[j], mx[i][0][j]=S[j];
		}
		nxt[i][0][N]=N, sum[i][0][N]=0, mx[i][0][N]=(1<<(i+1))-1;
		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]];
			sum[i][j][k]=sum[i][j-1][k]+sum[i][j-1][nxt[i][j-1][k]];
			mx[i][j][k]=min(mx[i][j-1][k], mx[i][j-1][nxt[i][j-1][k]]-sum[i][j-1][nxt[i][j-1][k]]);
		}
	}
}

long long simulate(int x, int z) {
	int k=x; ll v=z;
	for(int i=0; i<25; i++) {
		int kk=k; ll vv=v;
		for(int j=24; j>=0; j--) if(vv<=mx[i][j][kk]) vv+=sum[i][j][kk], kk=nxt[i][j][kk];
		if(vv<=mx[i][0][kk]) vv+=sum[i][0][kk], kk=nxt[i][0][kk];
		if(kk==N) {
			for(int j=24; j>=0; j--) if(nxt[i][j][k]!=N) v+=sum[i][j][k], k=nxt[i][j][k];
			if(k!=N) v+=sum[i][0][k], k=nxt[i][0][k];
			return v;
		}
		k=kk, v=vv;
	}
	return 0;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 297040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 306004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 306004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 306004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 306004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 306004 KB Output isn't correct
2 Halted 0 ms 0 KB -