Submission #960634

#TimeUsernameProblemLanguageResultExecution timeMemory
960634Trisanu_DasRainforest Jumps (APIO21_jumps)C++17
21 / 100
4061 ms15404 KiB
#include "jumps.h" #include<bits/stdc++.h> using namespace std; #include <vector> #define sz 200005 int n; vector<int> v; int dp[sz]; void init(int N, std::vector<int> H) { int i; n = N; for(i=0;i<N;i++) v.push_back(H[i]); } int FuN(int last,int C,int D) { if(last>=C && last<=D) return 0; if(dp[last]!=-1) return dp[last]; int ret = 1e9; for(int i=last+1;i<n;i++){ if(v[i]>v[last]){ ret = min(ret,1+FuN(i,C,D)); break; } } for(int i=last-1;i>=0;i--){ if(v[i]>v[last]){ ret = min(ret,1+FuN(i,C,D)); break; } } return dp[last] = ret; } int minimum_jumps(int A, int B, int C, int D) { memset(dp,-1,sizeof(dp)); int ans=1e9; for(int i=A;i<=B;i++) ans = min(ans,FuN(i,C,D)); if(ans==1e9) ans = -1; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...