Submission #1223434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223434		Jer	밀림 점프 (APIO21_jumps)	C++20	8 / 100	4035 ms	1824 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#include <vector>

using namespace std;

const int MAXN = 2005;
pair<int, int> con[MAXN];
int n;

bool vis[MAXN];
int solve(int s, int c, int d){

	for (int i = 0; i < n; i++)
		vis[i] = false;

	queue<int> q;
	q.push(s);

	int l = 0, curr, len;

	while (!q.empty())
	{
		len = q.size();
		for (int z = len; z > 0; z--){
			curr = q.front(), q.pop();

			if (vis[curr])
				continue;
			vis[curr] = true;

			if (curr >= c and curr <= d)
				return l;

			if (con[curr].first != -1)
				q.push(con[curr].first);

			if (con[curr].second != -1)
				q.push(con[curr].second);
		}
		l++;
	}

	return -1;
}

void init(int N, std::vector<int> H) {
	n = N;

	for (int i = 0; i < n; i++)
	{
		con[i].first = -1, con[i].second = -1;
		for (int j = i + 1; j < n; j++){
			if (H[i] < H[j])
				{con[i].second = j; break;}
		}

		for (int j = i - 1; j >= 0; j--){
			if (H[i] < H[j])
				{con[i].first = j; break;}
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	int res = -1, g;

	for (int i = A; i <= B; i++)
	{
		g = solve(i, C, D);
		if (g != -1)
			res = (res == -1) ? g : min(res, g);
	}

	return res;
}

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19