oj.uz

Submission #1011117

# Submission time Handle Problem Language Result Execution time Memory
1011117 2024-06-29T20:15:42 Z 1ne Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 263300 KB 
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int k = 20;
vector<vector<long long>>table;
vector<vector<long long>>nx;
vector<vector<long long>>sum;
vector<int>S,P,W,L;
long long N;	
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	table.resize(n,vector<long long>(k));
	nx.resize(n,vector<long long>(k,-1));
	sum.resize(n,vector<long long>(k,0));
	N = n;
	S = s;
	P = p;
	W = w;
	L = l;
	for (long long i = 0;i<n;++i){
		table[i][0] = s[i];
		nx[i][0] = w[i];
		sum[i][0] = s[i];
	}
	for (long long i = 1;i<k;++i){
			for (long long j = 0;j<n;++j){
			if (nx[j][i - 1] == -1 || nx[j][i - 1] == n)continue;
			//cout<<nx[j][i - 1]<<'\n';
			nx[j][i] = nx[nx[j][i - 1]][i - 1];
			table[j][i] = max(table[j][i - 1],table[nx[j][i - 1]][i - 1] - sum[j][i - 1]);
			sum[j][i] = sum[j][i - 1] + sum[nx[j][i - 1]][i - 1];
		}
	}
	return;
}
 
long long simulate(int x, int z) {
	long long Z = z;
	int cnt = 0;
	while(x != N){
		cnt++;
		//assert(cnt < 50);
	//	cout<<x<<"->";
		long long c = 0;
		while(nx[x][c] != -1 && table[x][c] <= Z){
			++c;
		}
		if (c != 0){
			Z+=sum[x][c - 1];
			x = nx[x][c - 1];
		}
		if (x != N && S[x] > Z){
			Z+=P[x];
			x = L[x];
		}	
	}
//	cout<<'\n';
	return Z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 1732 KB Output is correct
4 Correct 35 ms 33108 KB Output is correct
5 Correct 2 ms 1628 KB Output is correct
6 Correct 42 ms 33028 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 433 ms 261540 KB Output is correct
3 Correct 444 ms 261680 KB Output is correct
4 Correct 436 ms 263300 KB Output is correct
5 Correct 355 ms 263248 KB Output is correct
6 Correct 447 ms 261720 KB Output is correct
7 Correct 415 ms 259884 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 51 ms 34432 KB Output is correct
3 Correct 69 ms 34688 KB Output is correct
4 Correct 65 ms 33872 KB Output is correct
5 Correct 66 ms 33824 KB Output is correct
6 Execution timed out 7063 ms 34036 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 51 ms 34432 KB Output is correct
3 Correct 69 ms 34688 KB Output is correct
4 Correct 65 ms 33872 KB Output is correct
5 Correct 66 ms 33824 KB Output is correct
6 Execution timed out 7063 ms 34036 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 51 ms 34432 KB Output is correct
3 Correct 69 ms 34688 KB Output is correct
4 Correct 65 ms 33872 KB Output is correct
5 Correct 66 ms 33824 KB Output is correct
6 Execution timed out 7063 ms 34036 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 433 ms 261540 KB Output is correct
3 Correct 444 ms 261680 KB Output is correct
4 Correct 436 ms 263300 KB Output is correct
5 Correct 355 ms 263248 KB Output is correct
6 Correct 447 ms 261720 KB Output is correct
7 Correct 415 ms 259884 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 51 ms 34432 KB Output is correct
10 Correct 69 ms 34688 KB Output is correct
11 Correct 65 ms 33872 KB Output is correct
12 Correct 66 ms 33824 KB Output is correct
13 Execution timed out 7063 ms 34036 KB Time limit exceeded
14 Halted 0 ms 0 KB -