#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll
int t, n, m, k, h[5010], q, l, r;
struct cost{
int ft, sc, cost;
};
vector<cost> st[5001][5001];
int d[5001][5001];
bool btwn(int p1, int p2, int p3){
return ( (h[p1]>=min(h[p2], h[p3]) )&&(h[p1]<=max(h[p2], h[p3]) ) );
}
void combine(int p1, int l1, int p2, int l2){
if( (l1>=n) || (l2>=n) || ((min(min(l1, l2), min(p1, p2))<1) ) ){return;}
if( (!btwn(p1, l2, l2+1)) || (!btwn(p2, l1, l1+1)) || (!btwn(p1, l1, l1+1)) || (!btwn(p2, l2, l2+1)) ){return ;}
st[p1][l1].pb({p2, l2, abs(h[p1]-h[p2])});
return;
}
void edges(int pt, int ln){
if(!btwn(pt, ln+1, ln)){
return;
}
if(ln==n){return;}
if(pt==n){
if( btwn(pt-1, ln, ln+1) ){
combine(pt-1, ln,pt, ln);
}
if(btwn(ln+1, pt, pt-1)){
combine(ln+1, pt-1, pt, ln);
}
return;
}
if(pt==ln){
if(btwn(ln+1, pt-1, pt) ){
combine(ln+1, pt-1, pt, ln);
}
if(btwn(pt-1, ln, ln+1)){
combine(pt-1, ln, pt, ln);
}
return;
}
//inainte
//inainte
if(btwn(pt+1, ln, ln+1)){
combine(pt+1, ln, pt, ln);
}
if(btwn(ln+1, pt, pt+1)){
combine(ln+1, pt, ln, pt);
}
//inapoi
if(btwn(ln, pt, pt+1)){
combine(ln, pt, pt, ln);
}
if(btwn(pt+1, ln,ln+1)){
combine(pt+1, ln, pt, ln);
}
//inapoi
//inainte
if(btwn(pt-1, ln, ln+1)){
combine(pt-1, ln, pt, ln);
}
if(btwn(ln+1, pt, pt-1)){
combine(ln+1, pt-1, pt, ln);
}
//inapoi
if(btwn(pt-1, ln, ln+1)){
combine(pt-1, ln, pt, ln);
}
if(btwn(ln, pt, pt-1)){
combine(ln, pt-1, pt, ln);
}
return;
}
bool vr[5010][5010];
void dijkstra(){
d[n][1]=0;
multiset<pair<int, pii>> ms; ms.insert({0, {n, 1}});
while(!ms.empty()){
auto f=*ms.begin();
int x=f.sc.ft, y=f.sc.sc;
d[x][y]=f.ft;
vr[x][y]=true;
ms.erase(ms.begin());
for(auto nod:st[x][y]){
//cout<<"x"<<flush;
int u=nod.ft, v=nod.sc, c=nod.cost;
if(v==n){continue;}
if(vr[u][v]==true){continue;}
auto it=ms.find({d[u][v], {u, v}} );
if(it!=ms.end()){ms.erase(it);}
if(d[u][v]==-1){
d[u][v]=d[x][y]+c;
}
else{
d[u][v]=max(d[u][v], d[x][y]+c);
}
ms.insert({d[u][v], {u, v} } );
}
}
}
int32_t main(){
INIT
cin>>n;
for(int i=1; i<=n; i++){
cin>>h[i];
}
for(int x=1; x<=n; x++){
for(int y=x; y<=n; y++){
d[x][y]=-1;
edges(x, y);
}
}
/*for(int x=1; x<=n; x++){
for(int y=1; y<=n; y++){
cout<<x<<" "<<y<<": ";
for(auto g:st[x][y]){
cout<<"("<<g.ft<<" "<<g.sc<<" "<<g.cost<<") ";
}
cout<<"\n";
}
}*/
dijkstra();
int res=1e17;
for(int i=1; i<=n; i++){
if(d[i][i]!=(-1)){
res=min(res, d[i][i]);
}
}
if(res==1e17){cout<<"NO"; return 0;}
cout<<res;
return 0;
}
Compilation message
climbers.cpp: In function 'int32_t main()':
climbers.cpp:159:9: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
159 | int res=1e17;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
274 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
282 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
281 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
280 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
271 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
281 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
281 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
279 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
274 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
275 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
274 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
270 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
280 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
271 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
272 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
275 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
271 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
285 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
276 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
277 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
