제출 #1232657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232657		Timosh	던전 (IOI21_dungeons)	C++20	0 / 100	1 ms	1344 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.h"
#define ll int64_t

using namespace std;

int r = 27, N;

vector<vector<ll>> P, B, SP, SB, MNP, MNB;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
	N = n;
	s.push_back(0);
	p.push_back(0);
	l.push_back(n);
	w.push_back(n);
	P.resize(n + 1);
	MNP.resize(n + 1);
	// sum - s
	B.resize(n + 1);
	MNB.resize(n + 1);
	// sum - p
	for (auto &i : P)
		i.resize(r);
	for (auto &i : B)
		i.resize(r);
	for (auto &i : SP)
		i.resize(r);
	for (auto &i : SB)
		i.resize(r);
	for (auto &i : MNP)
		i.resize(r);
	for (auto &i : MNB)
		i.resize(r);
	for (int i = 0; i <= n; i++)
		P[i][0] = w[i];
	for (int i = 0; i <= n; i++)
		B[i][0] = l[i];
	for (int i = 0; i < n; i++)
		SP[i][0] = s[i];
	for (int i = 0; i < n; i++)
		SB[i][0] = p[i];
	for (int j = 1; j < r; j++)
		for (int i = 0; i <= n; i++)
			P[i][j] = P[P[i][j - 1]][j - 1];
	for (int j = 1; j < r; j++)
		for (int i = 0; i <= n; i++)
			B[i][j] = B[P[i][j - 1]][j - 1];
	for (int j = 1; j < r; j++)
		for (int i = 0; i <= n; i++)
			SP[i][j] = SP[i][j - 1] + SP[P[i][j - 1]][j - 1];
	for (int j = 1; j < r; j++)
		for (int i = 0; i <= n; i++)
			SB[i][j] = SB[i][j - 1] + SB[B[i][j - 1]][j - 1];
	for (int i = 0; i <= n; i++)
		MNP[i][0] = s[i] - s[w[i]];
	for (int i = 0; i <= n; i++)
		MNB[i][0] = p[i] - p[l[i]];
	for (int j = 1; j < r; j++)
		for (int i = 0; i <= n; i++)
			MNP[i][j] = min({MNP[i][j - 1], MNP[P[i][j - 1]][j - 1], SP[P[i][j]][j] - s[P[i][j]]});
	for (int j = 1; j < r; j++)
		for (int i = 0; i <= n; i++)
			MNB[i][j] = min({MNB[i][j - 1], MNB[P[i][j - 1]][j - 1], SB[P[i][j]][j] - p[P[i][j]]});
	return;
}

long long simulate(int x, int Z)
{
	ll z = Z;
	while (x < N)
	{
		for (int i = r - 1; i >= 0; i--)
			if (MNP[x][i] + z >= 0 && P[x][i] < N)
				z += SP[x][i], x = P[x][i];
		for (int i = r - 1; i >= 0; i--)
			if (MNB[x][i] + z >= 0 && B[x][i] < N)
				z += SB[x][i], x = B[x][i];
		if (x == N)
			break;
		if (z >= SP[x][0])
			z += SP[x][0], x = P[x][0];
		else
			z += SB[x][0], x = B[x][0];
	}
	return z;
}

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