Submission #643707

#	Time	Username	Problem	Language	Result	Execution time	Memory
643707		colossal_pepe	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4043 ms	9684 KiB

jumps

#include "jumps.h"

#include <vector>
#include <stack>
using namespace std;

const int INF = 1e9;

int n;
vector<int> prv, nxt;

int solve(int i, vector<int> &dp);

void init(int N, vector<int> h) {
  n = N;
  prv.resize(n), nxt.resize(n);
  stack<int> s;
  for (int i = 0; i < n; i++) {
    while (not s.empty() and h[s.top()] <= h[i]) s.pop();
    prv[i] = (s.empty() ? -1 : s.top());
    s.push(i);
  }
  while (not s.empty()) s.pop();
  for (int i = n - 1; i >= 0; i--) {
    while (not s.empty() and h[s.top()] <= h[i]) s.pop();
    nxt[i] = (s.empty() ? -1 : s.top());
    s.push(i);
  }

}

int minimum_jumps(int a, int b, int c, int d) {
  vector<int> dp(n, -1);
  for (int i = c; i <= d; i++) {
    dp[i] = 0;
  }
  int ans = INF;
  for (int i = a; i <= b; i++) {
    ans = min(ans, solve(i, dp));
  }
  return (ans == INF ? -1 : ans);
}

int solve(int i, vector<int> &dp) {
  if (i == -1) return INF;
  if (dp[i] != -1) return dp[i];
  dp[i] = min(1 + solve(prv[i], dp), 1 + solve(nxt[i], dp));
  return dp[i];
}

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