제출 #1238310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238310		walizamanee	던전 (IOI21_dungeons)	C++20	100 / 100	5311 ms	1976956 KiB

dungeons

#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;
using ll = long long;

long long dp[8][400003][26] , sum[8][400003][26]; // last er tate just answer rakhbo or something;
// minimum koto lagbe and kothai lagbe
long long ans[400003] , one , two , jog , ten[10];
int ek , dui , shesh[8][400001][26] , star , here , nn , pos[8][400003][26];
vector<int> sa , wa , pa , la;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l ) {
	sa = s;
	wa = w;
	la = l;
	pa = p;
	nn = n;
	ten[0] = 1;
	for( int z = 1; z <= 8; z++ ) ten[z] = ten[z - 1] * (ll)10;
	for( int z = 0; z <= 7; z++ ) {
		dp[z][n][0] = 0;
		pos[z][n][0] = n;
		sum[z][n][0] = 0;
		shesh[z][n][0] = n;
		for( int y = 0; y < n; y++ ){
			if( s[y] >= ten[z] ) {
				dp[z][y][0] = s[y];
				pos[z][y][0] = y;
				sum[z][y][0] = 0; //eta kheytal rakhio
				//shesh?
			} 
			else{
				dp[z][y][0] = 1e15;
				pos[z][y][0] = -1;
				sum[z][y][0] = 0; //eta kheytal rakhio
			}

		}
		for( int x = 1; x <= 25; x++ ) {
			dp[z][n][x] = 0;
			pos[z][n][x] = n;
			sum[z][n][x] = 0;
			shesh[z][n][x] = n;
			for( int y = 0; y < n; y++ ) {
				if( x == 1 ) {
					if( s[y] >= ten[z] ) {
						one = p[y];
						ek = l[y];
					} 
					else{
						one = s[y];
						ek = w[y];
					}
					sum[z][y][x] = one;
					dp[z][y][x] = dp[z][y][x - 1];
					pos[z][y][x] = pos[z][y][x - 1];
					shesh[z][y][x] = ek;
					if( dp[z][y][x] > (dp[z][ek][x - 1] - sum[z][y][x]) ) {
						dp[z][y][x] = (dp[z][ek][x - 1] - sum[z][y][x]);
						pos[z][y][x] = pos[z][ek][x - 1];
					}
				}
				else{
					sum[z][y][x] = sum[z][y][x - 1] + sum[z][shesh[z][y][x - 1]][x - 1];
					shesh[z][y][x] = shesh[z][shesh[z][y][x - 1]][x - 1];
					dp[z][y][x] = dp[z][y][x - 1];
					pos[z][y][x] = pos[z][y][x - 1];
					if( dp[z][y][x] > dp[z][shesh[z][y][x - 1]][x - 1] - sum[z][y][x - 1] ) {
						dp[z][y][x] = dp[z][shesh[z][y][x - 1]][x - 1] - sum[z][y][x - 1];
						pos[z][y][x] = pos[z][shesh[z][y][x - 1]][x - 1];
					}
				}
			} 
		}
	}
	ans[n] = 0;
	for( int z = n - 1; z >= 0; z-- ) {
		ans[z] = ans[w[z]] + s[z];
	}
	return;
}

long long simulate(int x, int zz) {
	here = (int)x;
	jog = (ll)zz;
	
	for( int z = 0; z <= 7; z++ ) {
		while( jog < ten[z + 1] && here != nn ) {

			for( int y = 25; y >= 1; y-- ) {
				if( dp[z][here][y] > jog ) {
					jog += sum[z][here][y];
					here = shesh[z][here][y];
					y++;
				}
			}
			if( dp[z][here][0] > jog ) {
				jog += sum[z][here][1];
				here = shesh[z][here][1];
			}
			if( here != nn ) { 
			jog += (ll)sa[here];
			here = wa[here];
			}
		}
	}
	if( here != nn ) jog += ans[here];
 	return jog;
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11