oj.uz

Submission #218857

# Submission time Handle Problem Language Result Execution time Memory
218857 2020-04-02T21:18:45 Z 2fat2code Climbers (RMI18_climbers) C++17
100 / 100
 209 ms 196344 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 5 ms 768 KB Output is correct
2 Correct 5 ms 2304 KB Output is correct
3 Correct 11 ms 12160 KB Output is correct
4 Correct 48 ms 82808 KB Output is correct
5 Correct 116 ms 196344 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 6 ms 3200 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 6 ms 2176 KB Output is correct
3 Correct 68 ms 11392 KB Output is correct
4 Correct 128 ms 76152 KB Output is correct
5 Correct 160 ms 75520 KB Output is correct
6 Correct 177 ms 137848 KB Output is correct
7 Correct 187 ms 130300 KB Output is correct
8 Correct 180 ms 186108 KB Output is correct
9 Correct 209 ms 188024 KB Output is correct
10 Correct 209 ms 185848 KB Output is correct