Submission #1101270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101270		blackslex	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4072 ms	21012 KiB

jumps

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

using namespace std;

const int MxN = 2e5 + 5;
int n, l[MxN], r[MxN];
vector<int> h;
bool sub1 = 1;

void init(int N, std::vector<int> H) {
  n = N; h = H;
  stack<int> st;
  for (int i = 0; i < n; i++) if (h[i] != i + 1) sub1 = 0;
  for (int i = 0; i < n; i++) {
    l[i] = -1;
    while (!st.empty() && h[i] > h[st.top()]) st.pop();
    if (!st.empty()) l[i] = st.top();
    st.emplace(i);
  }
  while (!st.empty()) st.pop();
  for (int i = n - 1; i >= 0; i--) {
    r[i] = -1;
    while (!st.empty() && h[i] > h[st.top()]) st.pop();
    if (!st.empty()) r[i] = st.top();
    st.emplace(i);
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  vector<vector<int>> dp(2, vector<int>(n + 5, 1e9));
  if (sub1) return C - B;
  for (int i = A; i <= B; i++) dp[0][i] = 0;
  int ans = 1e9;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < n; j++) dp[i & 1][j] = 1e9;
    for (int j = 0; j < n; j++) {
      if (~l[j]) dp[i & 1][l[j]] = min(dp[i & 1][l[j]], dp[!(i & 1)][j] + 1);
      if (~r[j]) dp[i & 1][r[j]] = min(dp[i & 1][r[j]], dp[!(i & 1)][j] + 1);
    }
    for (int j = 0; j < n; j++) cerr << dp[i & 1][j] << " \n"[j == n];
    for (int j = C; j <= D; j++) ans = min(ans, dp[i & 1][j]);
  }
  return (ans == 1e9 ? -1 : ans);
}

• Subtask 1: 0 / 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