oj.uz

Submission #602590

# Submission time Handle Problem Language Result Execution time Memory
602590 2022-07-23T09:05:15 Z rrrr10000 Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 231948 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef tuple<ll,ll,ll> PP;
typedef vector<PP> vpp;
typedef vector<vpp> vvpp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define pb emplace_back
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}

ll n;
vi s,p,w,l;
vvpp table;
PP f(PP a,PP b){
	chmax(get<1>(a),get<1>(b)-get<2>(a));
	get<2>(a)+=get<2>(b);
	get<0>(a)=get<0>(b);
	return a;
}
void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_){
	n=n_+1;
	for(ll x:s_)s.pb(x);
	for(ll x:p_)p.pb(x);
	for(ll x:w_)w.pb(x);
	for(ll x:l_)l.pb(x);
	s.pb(0);p.pb(0);w.pb(n-1);l.pb(n-1);
	table=vvpp(20,vpp(n));
	rep(i,n)table[0][i]=PP(w[i],s[i],s[i]);
	rep(i,19)rep(j,n)table[i+1][j]=f(table[i][j],table[i][get<0>(table[i][j])]);
	return;
}

long long simulate(int x_, int z_) {
	ll i=x_,cur=z_;
	/*
	while(i<n-1){
		if(cur>=s[i]){
			cur+=s[i];
			i=w[i];
		}
		else{
			cur+=p[i];
			i=l[i];
		}
	}
	*/
	while(i<n-1){
		if(cur<s[i]){
			cur+=p[i];i=l[i];
		}
		else{
			PP tmp(i,0,0);
			for(ll j=19;j>=0;j--){
				auto ntmp=f(tmp,table[j][get<0>(tmp)]);
				if(get<1>(ntmp)<=cur){
					tmp=ntmp;
				}
			}
			i=get<0>(tmp);cur+=get<2>(tmp);
		}
	}
	return cur;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 1364 KB Output is correct
4 Correct 38 ms 28100 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 31 ms 28112 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 293 ms 223452 KB Output is correct
3 Correct 292 ms 230440 KB Output is correct
4 Correct 297 ms 231932 KB Output is correct
5 Correct 303 ms 231948 KB Output is correct
6 Correct 335 ms 230360 KB Output is correct
7 Correct 294 ms 228628 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 55 ms 28928 KB Output is correct
3 Correct 60 ms 28884 KB Output is correct
4 Correct 53 ms 28932 KB Output is correct
5 Correct 50 ms 28880 KB Output is correct
6 Execution timed out 7063 ms 28944 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 852 KB Output is correct
2 Correct 55 ms 28928 KB Output is correct
3 Correct 60 ms 28884 KB Output is correct
4 Correct 53 ms 28932 KB Output is correct
5 Correct 50 ms 28880 KB Output is correct
6 Execution timed out 7063 ms 28944 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 852 KB Output is correct
2 Correct 55 ms 28928 KB Output is correct
3 Correct 60 ms 28884 KB Output is correct
4 Correct 53 ms 28932 KB Output is correct
5 Correct 50 ms 28880 KB Output is correct
6 Execution timed out 7063 ms 28944 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 293 ms 223452 KB Output is correct
3 Correct 292 ms 230440 KB Output is correct
4 Correct 297 ms 231932 KB Output is correct
5 Correct 303 ms 231948 KB Output is correct
6 Correct 335 ms 230360 KB Output is correct
7 Correct 294 ms 228628 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 55 ms 28928 KB Output is correct
10 Correct 60 ms 28884 KB Output is correct
11 Correct 53 ms 28932 KB Output is correct
12 Correct 50 ms 28880 KB Output is correct
13 Execution timed out 7063 ms 28944 KB Time limit exceeded
14 Halted 0 ms 0 KB -