제출 #568244

#제출 시각아이디문제언어결과실행 시간메모리
568244Aktan밀림 점프 (APIO21_jumps)C++14
21 / 100
48 ms4240 KiB
#include "jumps.h" #include <bits/stdc++.h> #ifndef EVAL #include "stub.cpp" #endif using namespace std; int n; bool h=0; vector<int> a; int b[2005],c[2005]; void init(int N, vector<int> H) { n=N; a=H; for(int i=0;i<n;i++){ if(i){ if(H[i]!=H[i-1]+1){ h=1; break; } } } deque<int> s; for(int i=0;i<n;i++){ while(!s.empty() && a[s.back()]<a[i]){ s.pop_back(); } if(s.empty()){ b[i]=-1; } else{ b[i]=s.back(); } s.push_back(i); } s.clear(); for(int i=n-1;i>=0;i--){ while(!s.empty() && a[s.back()]<a[i]){ s.pop_back(); } if(s.empty()){ c[i]=-1; } else{ c[i]=s.back(); } s.push_back(i); } } int ans[2005]; int minimum_jumps(int A, int B, int C, int D) { if(h==0){ return C-B; } else{ for(int i=0;i<n;i++){ ans[i]=1e9; } queue<int> q; for(int i=A;i<=B;i++){ ans[i]=0; q.push(i); } while(!q.empty()){ int to=q.front(); q.pop(); if(b[to]!=-1 && ans[b[to]]>ans[to]+1){ ans[b[to]]=ans[to]+1; q.push(b[to]); } if(c[to]!=-1 && ans[c[to]]>ans[to]+1){ ans[c[to]]=ans[to]+1; q.push(c[to]); } } int k=1e9; for(int i=C;i<=D;i++){ k=min(k,ans[i]); } if(k==1e9){ return -1; } else{ return k; } } }
#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...