Submission #566880

#	Time	Username	Problem	Language	Result	Execution time	Memory
566880		Turkhuu	Rainforest Jumps (APIO21_jumps)	C++17	8 / 100	4053 ms	1048576 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1000000;
int n;
vector<int> a;
vector<vector<int>> d;
void init(int N, vector<int> H){
  n = N;
  a = H;
  d.assign(n, vector(n, inf));
  for(int i = 0; i < n; i++){
    int l = i - 1;
    while(l >= 0 && a[l] <= a[i]){
      l--;
    }
    if(l >= 0){
      d[i][l] = 1;
    }
    int r = i + 1;
    while(r < n && a[r] <= a[i]){
      r++;
    }
    if(r < n){
      d[i][r] = 1;
    }
  }
  for(int k = 0; k < n; k++){
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        if(d[i][k] + d[k][j] < d[i][j]){
          d[i][j] = d[i][k] + d[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, d[i][j]);
    }
  }
  if(ans == inf){
    ans = -1;
  }
  return ans;
}

• 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