This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
#define int long long
const int mod=1e9+7,inf=1e9+1;
const i64 INF=1e18;
struct node
{
int nod1,nod2;
long long cost;
bool operator <(const node& b) const
{
return cost>b.cost;
}
};
bool same_type_diff(int a,int b,int c)
{
return (a<=b && b<=c) || (a>=b && b>=c);
}
void modify_h(vector<int>&h)
{
vector<int>sol;
for(auto &c:h)
{
while(sol.size()>=2 && same_type_diff(sol[sol.size()-2],sol.back(),c))
{
sol.pop_back();
}
sol.push_back(c);
}
h=sol;
}
main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
vector<int>h(n);
for(auto &c:h)
{
cin>>c;
}
modify_h(h);
n=(int)h.size();
priority_queue<node>q;
vector<vector<i64>>dist(n,vector<i64>(n-1,INF));
dist[0][n-2]=0;
q.push({0,n-2,0});
auto add=[&](int x,int y,i64 cost)
{
if(dist[x][y]>cost)
{
dist[x][y]=cost;
q.push({x,y,cost});
}
};
while(q.size())
{
auto then=q.top();
q.pop();
int nod1=then.nod1,nod2=then.nod2;
if(then.cost != dist[nod1][nod2])
{
continue;
}
if(nod1==nod2 || nod1==nod2+1)
{
cout<<then.cost;
return 0;
}
int capat_min=min(h[nod2],h[nod2+1]);
int capat_max=max(h[nod2],h[nod2+1]);
int capat_min_poz=nod2;
int capat_max_poz=nod2+1;
if(capat_min!=h[capat_min_poz])
{
swap(capat_min_poz,capat_max_poz);
}
//e minim local
if(nod1==0 || h[nod1]<h[nod1-1])
{
//merg spre nod1-1
if(nod1>0)
{
int minn=min(h[nod1-1] , capat_max);
if(minn==h[nod1-1])
{
add(nod1-1,nod2,then.cost+abs(minn-h[nod1]));
}
if(minn==capat_max)
{
add(capat_max_poz,nod1-1,then.cost+abs(minn-h[nod1]));
}
}
if(nod1<n-1)
{
int minn=min(h[nod1+1] , capat_max);
if(minn==h[nod1+1])
{
add(nod1+1,nod2,then.cost+abs(minn-h[nod1]));
}
if(minn==capat_max)
{
add(capat_max_poz,nod1,then.cost+abs(minn-h[nod1]));
}
}
}
else
{
if(nod1>0)
{
int minn=max(h[nod1-1] , capat_min);
if(minn==h[nod1-1])
{
add(nod1-1,nod2,then.cost+abs(minn-h[nod1]));
}
if(minn==capat_min)
{
add(capat_min_poz,nod1-1,then.cost+abs(minn-h[nod1]));
}
}
if(nod1<n-1)
{
int minn=max(h[nod1+1] , capat_min);
if(minn==h[nod1+1])
{
add(nod1+1,nod2,then.cost+abs(minn-h[nod1]));
}
if(minn==capat_min)
{
add(capat_min_poz,nod1,then.cost+abs(minn-h[nod1]));
}
}
}
}
cout<<"NO";
}
Compilation message (stderr)
climbers.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
38 | main()
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |