#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;
const int mod=1e9+7;
const int modp=1999999973;
const int modulo=998244353;
const int nmax=5005;
int n,a[nmax],dist[nmax][nmax];
void removeinutil(){
vector<int>tz;
for(int i=1;i<=n;i++){
if(i>=2 && i<n){
if(a[i-1]<=a[i] && a[i]<=a[i+1]) continue;
if(a[i-1]>=a[i] && a[i]>=a[i+1]) continue;
}
tz.push_back(a[i]);
}
for(int i=tz.size()+1;i<=n;i++) a[i]=0;
n=tz.size();
for(int i=1;i<=n;i++) a[i]=tz[i-1];
}
struct Perechi{
int nod,edge,cost;
bool operator < (Perechi const &a) const{
return cost > a.cost;
}
};
priority_queue<Perechi>pq;
void addedge(int nod,int edge,int cost){
if(cost<dist[nod][edge]){
dist[nod][edge]=cost;
pq.push({nod,edge,cost});
}
return;
}
bool check(int nod,int edge){
if(a[edge]<a[edge+1]){
return (a[edge]<=a[nod] && a[nod]<=a[edge+1]);
}
else{
return (a[edge]>=a[nod] && a[nod]>=a[edge+1]);
}
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
srand(chrono::steady_clock::now().time_since_epoch().count());
// ifstream cin("input.in");
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
removeinutil();
for(int i=1;i<=n;i++)
for(int j=1;j<n;j++)
dist[i][j]=1e18;
dist[1][n-1]=0;
pq.push({1,n-1,0});
while(pq.size()){
int nod=pq.top().nod;
int edge=pq.top().edge;
int cost=pq.top().cost;
pq.pop();
if(nod==edge || nod==(edge+1)){
cout << cost << '\n';
return 0;
}
if(cost==dist[nod][edge]){
if(nod<n && check(nod+1,edge)){
addedge(nod+1,edge,cost+abs(a[nod+1]-a[nod]));
}
if(nod>1 && check(nod-1,edge)){
addedge(nod-1,edge,cost+abs(a[nod-1]-a[nod]));
}
if(check(edge,nod)){
addedge(edge,nod,cost+abs(a[nod]-a[edge]));
}
if(nod>1 && check(edge,nod-1)){
addedge(edge,nod-1,cost+abs(a[edge]-a[nod]));
}
if(check(edge+1,nod)){
addedge(edge+1,nod,cost+abs(a[nod]-a[edge+1]));
}
if(nod>1 && check(edge+1,nod-1)){
addedge(edge+1,nod-1,cost+abs(a[nod]-a[edge+1]));
}
}
}
cout << -1 << '\n';
return 0;
Compilation message
climbers.cpp: In function 'int32_t main()':
climbers.cpp:109:13: error: expected '}' at end of input
109 | return 0;
| ^
climbers.cpp:66:15: note: to match this '{'
66 | int32_t main(){
| ^
