Submission #1177531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177531		tkm_algorithms	Rainforest Jumps (APIO21_jumps)	C++20	8 / 100	11 ms	1964 KiB

jumps

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
//#define int ll
const char nl = '\n';
const int N = 3e5;
const int inf = 1e9;

int dp[201][201];

void init(int n, vector<int> h) {
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) {
			if (i == j)continue;
			dp[i][j] = inf;
		}
		
	stack<int> st;
	vector<int> a(n, -1), b(n, -1);
	for (int i = n-1; i >= 0; --i) {
		while (!st.empty() && h[st.top()] <= h[i])st.pop();
		
		if (!st.empty())a[i] = st.top();
		st.push(i);
	}
	
	while (!st.empty())st.pop();
	
	for (int i = 0; i < n; ++i) {
		while (!st.empty() && h[st.top()] <= h[i])st.pop();
		
		if (!st.empty())b[i] = st.top();
		st.push(i);
	}
	
	for (int i = 0; i < n; ++i) {
		if (a[i] != -1)dp[i][a[i]] = 1;
		if (b[i] != -1)dp[i][b[i]] = 1;
	}
	
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				if (dp[i][k] < inf && dp[k][j] < inf)
					dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
	}
}

int minimum_jumps(int a, int b, int c, int d) {
	int ans = inf;
	for (int i = a; i <= b; ++i)
		for (int j = c; j <= d; ++j) {
			ans = min(ans, dp[i][j]);
		}
		
	if (ans == inf)ans = -1;
	return ans;
}


//int main() {
	//stack<int> st;
	
	//int n; cin >> n;
	//vector<int> a(n, -1), b(n, -1);
	//vector<int> h(n);
	//for (auto &i: h)cin >> i;
	
	//for (int i = 0; i < n; ++i)
		//for (int j = 0; j < n; ++j) {
			//if (i == j)continue;
			//dp[i][j] = inf;
		//}
		
	//for (int i = n-1; i >= 0; --i) {
		//while (!st.empty() && h[st.top()] <= h[i])st.pop();
		
		//if (!st.empty())a[i] = st.top();
		//st.push(i);
	//}
	
	//while (!st.empty())st.pop();
	
	//for (int i = 0; i < n; ++i) {
		//while (!st.empty() && h[st.top()] <= h[i])st.pop();
		
		//if (!st.empty())b[i] = st.top();
		//st.push(i);
	//}
	
	
	//for (int i = 0; i < n; ++i) {
		//if (a[i] != -1)dp[i][a[i]] = 1;
		//if (b[i] != -1)dp[i][b[i]] = 1;
		
	//}
	
	//for (int k = 0; k < n; ++k) {
		//for (int i = 0; i < n; ++i)
			//for (int j = 0; j < n; ++j)
				//if (dp[i][k] < inf && dp[k][j] < inf) {
					//dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
				//}
	//}
	
	//int q; cin >> q;
	//while (q--) {
		//int x, y, c, d;
		//cin >> x >> y >> c >> d;
		
		//int ans = inf;
		//for (int i = x; i <= y; ++i)
			//for (int j = c; j <= d; ++j)
				//ans = min(ans, dp[i][j]);
				
		//if (ans == inf)ans = -1;
		//cout << ans << nl;
	//}
	//return 0;
//}

• 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