#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#define ll long long
//#define int ll
#define ull unsigned ll
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define chkmin(a,b) (a=min(a,b))
#define chkmax(a,b) (a=max(a,b))
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
template <int mod>
struct Modint{
int val;
Modint(int _val=0){val=_val%mod;if(val<0) val+=mod;}
Modint operator +(const Modint& o) const {
Modint res;
res.val=val+o.val;
if(res.val>=mod) res.val-=mod;
return res;
}
Modint operator +(const int& o) const {return Modint(val+o);}
Modint operator -() const {
Modint res;
res.val=-val;
if(res.val<0) res.val+=mod;
return res;
}
Modint operator -(const Modint& o) const {
Modint res;
res.val=val-o.val;
if(res.val<0) res.val+=mod;
return res;
}
Modint operator -(const int& o) const {return Modint(val-o);}
Modint operator *(const Modint& o) const {return Modint(val*o.val);}
Modint operator *(const int& o) const {return Modint(val*(o%mod));}
Modint operator +=(const Modint& o){*this=(*this)+o;return *this;}
Modint operator -=(const Modint& o){*this=(*this)-o;return *this;}
Modint operator *=(const Modint& o){*this=(*this)*o;return *this;}
Modint Pow(int b) const {
Modint tmp(val),ret(1);
while(b){
if(b&1) ret*=tmp;
b>>=1;tmp*=tmp;
}
return ret;
}
Modint Pow(const Modint& a, int b) const {return a.Pow(b);}
inline Modint inv() const {return (*this).Pow(mod-2);}
Modint operator /(const Modint& o) const {return *this*o.inv();}
Modint operator /(const int& o) const {return *this*Modint(o).inv();}
bool operator ==(const Modint& o) const {return val==o.val;}
};
template<int mod>
ostream& operator << (ostream& o, Modint<mod> x){return o << x.val;}
template<int mod>
Modint<mod> operator +(const int& x, const Modint<mod>& y){return Modint<mod>(x+y.val);}
template<int mod>
Modint<mod> operator -(const int& x, const Modint<mod>& y){return Modint<mod>(x-y.val);}
template<int mod>
Modint<mod> operator *(const int& x, const Modint<mod>& y){return Modint<mod>(x%mod*y.val);}
#define modint Modint<MOD>
vector<modint> inv,fac,invfac;
void init_comb(int N){
inv.resize(N),fac.resize(N),invfac.resize(N);
inv[1]=1,fac[0]=1,invfac[0]=1;
rep2(i,2,N) inv[i]=inv[MOD%i]*(MOD-MOD/i);
rep2(i,1,N) fac[i]=fac[i-1]*i;
rep2(i,1,N) invfac[i]=invfac[i-1]*inv[i];
}
inline modint C(int n, int m){return m>n||m<0?modint(0):fac[n]*invfac[m]*invfac[n-m];}
inline modint H(int n, int m){return C(n+m-1,n);}
const int maxn=5005,maxm=32,maxk=7777714;
//i_am_noob
//#define wiwihorz
int n,a[maxn];
ll dis[maxn*maxn];
bool vis[maxn*maxn];
#define DE pair<ll,int>
priority_queue<DE,vector<DE>,greater<DE>> pq;
void Insert(ll d, int x, int y){
int val=x*n+y;
if(d<dis[val]){
dis[val]=d;
pq.push({d,val});
}
}
void orzck(){
cin >> n;
rep(n) cin >> a[i];
vector<int> vec;
rep(n){
if(i>0&&a[i]==a[i-1]) continue;
while(sz(vec)>1&&((vec[sz(vec)-2]-vec.back()>0)^(vec.back()-a[i]>0)^1)) vec.pop_back();
vec.pb(a[i]);
}
n=sz(vec);
rep(n) a[i]=vec[i];
rep(n-1) assert(a[i]!=a[i+1]);
rep2(i,1,n-1) assert((a[i-1]-a[i]>0)^(a[i]-a[i+1]>0));
rep(maxn*maxn) dis[i]=inf;
dis[n-1]=0;
pq.push({0,n-1});
while(!pq.empty()){
auto [d,tmp]=pq.top(); pq.pop();
int x=tmp/n,y=tmp%n;
if(x==y){
print(d);
return;
}
if(vis[tmp]) continue;
vis[tmp]=1;
bug(x,y,d);
int cur=a[x];
if(a[x]==a[y]){
if(x>0&&y>0){
int val1=abs(a[x-1]-cur),val2=abs(a[y-1]-cur);
if(val1<=val2) Insert(d+val1,x-1,y-1);
else Insert(d+val2,y-1,x-1);
}
if(x>0&&y<n-1){
int val1=abs(a[x-1]-cur),val2=abs(a[y+1]-cur);
if(val1==val2) Insert(d+val1,x-1,y+1);
else if(val1<=val2) Insert(d+val1,x-1,y);
else Insert(d+val2,y+1,x-1);
}
if(x<n-1&&y>0){
int val1=abs(a[x+1]-cur),val2=abs(a[y-1]-cur);
if(val1<=val2) Insert(d+val1,x+1,y-1);
else Insert(d+val2,y-1,x);
}
if(x<n-1&&y<n-1){
int val1=abs(a[x+1]-cur),val2=abs(a[y+1]-cur);
if(val1==val2) Insert(d+val1,x+1,y+1);
else if(val1<=val2) Insert(d+val1,x+1,y);
else Insert(d+val2,y+1,x);
}
continue;
}
if(((a[y]-cur>0)^(x&1))){
if(x>0){
int val1=abs(a[x-1]-cur),val2=abs(a[y]-cur);
if(val1<=val2) Insert(d+val1,x-1,y);
else Insert(d+val2,y,x-1);
}
if(x<n-1){
int val1=abs(a[x+1]-cur),val2=abs(a[y]-cur);
if(val1<=val2) Insert(d+val1,x+1,y);
else Insert(d+val2,y,x);
}
}
else{
if(x>0){
int val1=abs(a[x-1]-cur),val2=abs(a[y+1]-cur);
if(val1==val2) Insert(d+val1,x-1,y+1);
else if(val1<=val2) Insert(d+val1,x-1,y);
else Insert(d+val2,y+1,x-1);
}
if(x<n-1){
int val1=abs(a[x+1]-cur),val2=abs(a[y+1]-cur);
if(val1==val2) Insert(d+val1,x+1,y+1);
else if(val1<=val2) Insert(d+val1,x+1,y);
else Insert(d+val2,y+1,x);
}
}
}
print("NO");
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0);
// #ifdef i_am_noob
// freopen("input1.txt","r",stdin);
// freopen("output1.txt","w",stdout);
// freopen("output2.txt","w",stderr);
// #endif
cout << fixed << setprecision(15);
int t;
#ifdef wiwihorz
cin >> t;
#else
t=1;
#endif
ld start=clock();
while(t--) orzck();
bug((clock()-start)/CLOCKS_PER_SEC);
return 0;
}
Compilation message
climbers.cpp: In function 'void orzck()':
climbers.cpp:34:18: warning: statement has no effect [-Wunused-value]
34 | #define bug(...) 777771449
| ^~~~~~~~~
climbers.cpp:147:9: note: in expansion of macro 'bug'
147 | bug(x,y,d);
| ^~~
climbers.cpp: In function 'int main()':
climbers.cpp:34:18: warning: statement has no effect [-Wunused-value]
34 | #define bug(...) 777771449
| ^~~~~~~~~
climbers.cpp:220:5: note: in expansion of macro 'bug'
220 | bug((clock()-start)/CLOCKS_PER_SEC);
| ^~~
climbers.cpp:218:8: warning: unused variable 'start' [-Wunused-variable]
218 | ld start=clock();
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
196344 KB |
Output is correct |
| 2 |
Correct |
69 ms |
196356 KB |
Output is correct |
| 3 |
Correct |
78 ms |
197296 KB |
Output is correct |
| 4 |
Correct |
80 ms |
205212 KB |
Output is correct |
| 5 |
Correct |
109 ms |
220576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
196292 KB |
Output is correct |
| 2 |
Correct |
70 ms |
196368 KB |
Output is correct |
| 3 |
Correct |
75 ms |
196392 KB |
Output is correct |
| 4 |
Correct |
68 ms |
196352 KB |
Output is correct |
| 5 |
Correct |
77 ms |
196652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
196384 KB |
Output is correct |
| 2 |
Correct |
70 ms |
196380 KB |
Output is correct |
| 3 |
Correct |
98 ms |
197268 KB |
Output is correct |
| 4 |
Correct |
121 ms |
204344 KB |
Output is correct |
| 5 |
Correct |
127 ms |
204360 KB |
Output is correct |
| 6 |
Correct |
127 ms |
211616 KB |
Output is correct |
| 7 |
Correct |
131 ms |
210616 KB |
Output is correct |
| 8 |
Correct |
130 ms |
218080 KB |
Output is correct |
| 9 |
Correct |
151 ms |
217668 KB |
Output is correct |
| 10 |
Correct |
138 ms |
217708 KB |
Output is correct |
