Submission #982528

#	Time	Username	Problem	Language	Result	Execution time	Memory
982528		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	4043 ms	9104 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int n, L[200001], R[200001], dp[200001];
bool subtask1;
vector<int> g[200001];
void init(int N, std::vector<int> H) {
	n = N;
	stack<int> st;
	subtask1 = 1;
	for (int i = 0; i < N; i++) {
		if (H[i] != i + 1) subtask1 = 0;
	}
	//for (int i = 0; i < N; i++) {
		//while (st.size() && H[st.top()] <= H[i]) st.pop();
		//if (st.size()) L[i] = st.top();
		//else L[i] = -1;
		//st.push(i);
	//}
	for (int i = N - 1; i >= 0; i--) {
		while (st.size() && H[st.top()] <= H[i]) st.pop();
		if (st.size()) R[i] = st.top();
		else R[i] = -1;
		st.push(i);
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	if (subtask1) return C - B;
	int ans = 1e9;
	for (int i = A; i <= B; i++) {
		for (int j = 0; j < n; j++) dp[j] = 1e9;
		for (int j = i; j >= 0; j--) {
			if (L[j] != -1) dp[L[j]] = min(dp[L[j]], dp[j] + 1);
		}
		dp[i] = 0;
		for (int j = 0; j < n; j++) {
			if (R[j] != -1) dp[R[j]] = min(dp[R[j]], dp[j] + 1);
		}
		for (int j = C; j <= D; j++) ans = min(ans, dp[j]);
	}
  return (ans < 5e8 ? ans : -1);
}

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