Submission #477897

#	Time	Username	Problem	Language	Result	Execution time	Memory
477897		stefantaga	Climbers (RMI18_climbers)	C++14	100 / 100	212 ms	196336 KiB

climbers

#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;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 50 / 50