oj.uz

Submission #477897

# Submission time Handle Problem Language Result Execution time Memory
477897 2021-10-04T13:47:57 Z stefantaga Climbers (RMI18_climbers) C++14
100 / 100
 212 ms 196336 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 2 ms 2128 KB Output is correct
3 Correct 7 ms 12112 KB Output is correct
4 Correct 44 ms 82696 KB Output is correct
5 Correct 122 ms 196336 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 976 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 2 ms 3016 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 2 ms 2000 KB Output is correct
3 Correct 81 ms 11408 KB Output is correct
4 Correct 140 ms 76072 KB Output is correct
5 Correct 171 ms 75532 KB Output is correct
6 Correct 182 ms 137768 KB Output is correct
7 Correct 183 ms 130244 KB Output is correct
8 Correct 173 ms 186056 KB Output is correct
9 Correct 212 ms 187952 KB Output is correct
10 Correct 211 ms 185804 KB Output is correct