#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define rep(i, a, b) for(ll i = a; i < ll(b); ++i)
#define rrep(i, a, b) for(ll i = b-1; i >= ll(a); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
ll n;
vi h;
ll lower(ll s){
if(h[s]<h[s+1]) return s;
else return s+1;
}
ll upper(ll s){
if(h[s]<h[s+1]) return s+1;
else return s;
}
struct Node {
ll v,s;
pair<ll, Node> makeEdge(ll v,Node newNode){
return {abs(h[v]-h[newNode.v]),newNode};
}
vector<pair<ll,Node>> edges(){
vector<pair<ll,Node>> ret;
if(h[v+1]<h[v]){
ll mnS = min(h[s],h[s+1]);
if(mnS>=h[v+1])
ret.emplace_back(makeEdge(v,Node({lower(s),v})));
if(mnS<=h[v+1])
ret.emplace_back(makeEdge(v,Node({v+1,s})));
if(mnS>=h[v-1])
ret.emplace_back(makeEdge(v,Node({lower(s),v-1})));
if(mnS<=h[v-1])
ret.emplace_back(makeEdge(v,Node({v-1,s})));
} else {
ll mxS = max(h[s],h[s+1]);
if(mxS<=h[v+1])
ret.emplace_back(makeEdge(v,Node({upper(s),v})));
if(mxS>=h[v+1])
ret.emplace_back(makeEdge(v,Node({v+1,s})));
if(mxS<=h[v-1])
ret.emplace_back(makeEdge(v,Node({upper(s),v-1})));
if(mxS>=h[v-1])
ret.emplace_back(makeEdge(v,Node({v-1,s})));
}
if(h[v]==h[s]) {
ret.emplace_back(makeEdge(v,Node({s,v})));
ret.emplace_back(makeEdge(v,Node({s,v-1})));
}
if(h[v]==h[s+1]) {
ret.emplace_back(makeEdge(v,Node({s+1,v})));
ret.emplace_back(makeEdge(v,Node({s+1,v-1})));
}
//cout<<v<<" "<<s<<": ";
//trav(r,ret) cout<<"("<<r.second.v<<","<<r.second.s<<") ";
//cout<<endl;
return ret;
}
bool invalid(){
return v==0||v==n-1||s==0||s==n-2;
}
};
bool operator <(const Node& x, const Node& y) {
return tie(x.v,x.s)<tie(y.v,y.s);
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
srand(1);
cin>>n;
vi htemp;
rep(i,0,n) {
ll x;
cin>>x;
//x = rand()%10;
//if(i==0||i==n-1) x = 0;
//cout<<x<<" ";
if(!htemp.size()||htemp.back()!=x) htemp.push_back(x);
}
//cout<<endl;
h.push_back(1e9);
h.push_back(0);
rep(i,1,htemp.size()-1){
if((htemp[i]<htemp[i-1])==(htemp[i]<htemp[i+1])){
h.push_back(htemp[i]);
}
}
h.push_back(0);
h.push_back(1e9);
//trav(hi,h) cout<<hi<<" ";
//cout<<endl;
n = h.size();
priority_queue<pair<ll,Node>,vector<pair<ll,Node>>,greater<pair<ll,Node>>> q;
vector<vector<bool>> seen(n,vector<bool>(n));
q.emplace(0,Node({1,n-3}));
while(q.size()){
ll d = q.top().first;
Node V = q.top().second;
q.pop();
//cout<<d<<": "<<V.v<<" "<<V.s<<endl;
if(seen[V.v][V.s]||V.invalid()) continue;
seen[V.v][V.s] = true;
if(V.v==V.s||V.v-1==V.s){
cout<<d<<endl;
return 0;
}
trav(e,V.edges()){
if(seen[e.second.v][e.second.s]||e.second.invalid()) continue;
q.emplace(d+e.first,e.second);
}
}
assert(false);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
8 ms |
508 KB |
Output is correct |
| 4 |
Correct |
18 ms |
1656 KB |
Output is correct |
| 5 |
Correct |
60 ms |
3704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
380 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
0 ms |
376 KB |
Output is correct |
| 3 |
Correct |
381 ms |
764 KB |
Output is correct |
| 4 |
Correct |
488 ms |
1656 KB |
Output is correct |
| 5 |
Correct |
737 ms |
1628 KB |
Output is correct |
| 6 |
Correct |
695 ms |
2552 KB |
Output is correct |
| 7 |
Correct |
784 ms |
2552 KB |
Output is correct |
| 8 |
Correct |
544 ms |
3576 KB |
Output is correct |
| 9 |
Correct |
712 ms |
3576 KB |
Output is correct |
| 10 |
Execution timed out |
827 ms |
3576 KB |
Time limit exceeded |
