oj.uz

Submission #1046077

# Submission time Handle Problem Language Result Execution time Memory
1046077 2024-08-06T09:46:41 Z Unforgettablepl Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 263252 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e15;

vector<int> s,p,w,l;
vector<vector<int>> lift;
vector<vector<long long>> liftcost;
vector<vector<long long>> liftneed;
int n;

void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l){
	::n=n;
	::s=s;
	::p=p;
	::w=w;
	::l=l;
	lift = vector(n+1,vector(24,0));
	liftcost = vector(n+1,vector(24,0ll));
	liftneed = vector(n+1,vector(24,0ll));
	for(int i=0;i<n;i++){
		lift[i][0] = w[i];
		liftcost[i][0] = s[i];
		liftneed[i][0] = s[i];
	}
	liftcost[n][0]=INF;
	liftneed[n][0]=INF;
	lift[n][0]=n;
	for(int bit=1;bit<24;bit++){
		for(int i=0;i<=n;i++){
			lift[i][bit]=lift[lift[i][bit-1]][bit-1];
			liftcost[i][bit]=liftcost[i][bit-1]+liftcost[lift[i][bit-1]][bit-1];
			liftneed[i][bit]=max(liftneed[i][bit-1],liftneed[lift[i][bit-1]][bit-1]-liftcost[i][bit-1]);
		}
	}
	return;
}

long long simulate(int x,int z){
	while(x!=n){		
		for(int bit=23;bit>=0;bit--){
			if(z>=liftneed[x][bit]){
				z+=liftcost[x][bit];
				x=lift[x][bit];
			}
		}
		if(x==n)return z;
		z += p[x];
		x = l[x];
	}
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 31 ms 32156 KB Output is correct
5 Correct 2 ms 1628 KB Output is correct
6 Correct 32 ms 32092 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 392 ms 254780 KB Output is correct
3 Correct 397 ms 261712 KB Output is correct
4 Correct 386 ms 263252 KB Output is correct
5 Correct 371 ms 263224 KB Output is correct
6 Correct 417 ms 261712 KB Output is correct
7 Correct 398 ms 259920 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 48 ms 32948 KB Output is correct
3 Execution timed out 7077 ms 32740 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 48 ms 32948 KB Output is correct
3 Execution timed out 7077 ms 32740 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 48 ms 32948 KB Output is correct
3 Execution timed out 7077 ms 32740 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 392 ms 254780 KB Output is correct
3 Correct 397 ms 261712 KB Output is correct
4 Correct 386 ms 263252 KB Output is correct
5 Correct 371 ms 263224 KB Output is correct
6 Correct 417 ms 261712 KB Output is correct
7 Correct 398 ms 259920 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 48 ms 32948 KB Output is correct
10 Execution timed out 7077 ms 32740 KB Time limit exceeded
11 Halted 0 ms 0 KB -