oj.uz

답안 #336694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
336694 2020-12-16T12:35:00 Z Sorting Climbers (RMI18_climbers) C++17
0 / 100
 124 ms 215916 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 5000 + 3;
const ll INF = 1e18;

void build_edges(int pos1, int pos2, bool exact, vector<array<ll, 4>> &adj);

int n, a[N];
ll dist[N][N][2];
bool dp[N][N][2];

ll dijkstra(int pos1, int pos2, bool exact){
    priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;

    for(int pos1 = 0; pos1 < n; ++pos1)
        for(int pos2 = pos1; pos2 < n; ++pos2)
            for(int exact = 0; exact <= 1; ++exact)
                dist[pos1][pos2][exact] = INF;

    dist[pos1][pos2][exact] = 0;
    pq.push({0, pos1, pos2, exact});

    vector<array<ll, 4>> adj;
    while(!pq.empty()){
        auto [d, pos1, pos2, exact] = pq.top();
        pq.pop();

        if(d != dist[pos1][pos2][exact]) continue;
        if(pos1 == pos2) return d;

        adj.clear();
        build_edges(pos1, pos2, exact, adj);
        for(auto [pos1_to, pos2_to, exact_to, cost]: adj){
            ll cand = d + cost;
            if(cand < dist[pos1_to][pos2_to][exact_to]){
                dist[pos1_to][pos2_to][exact_to] = cand;
                pq.push({cand, pos1_to, pos2_to, exact_to});
            } 
        }
    }

    return INF;
}

void move_dp(int mv1, int mv2, int pos1, int pos2, bool exact, int x, vector<array<ll, 4>> &adj){
    //cout << mv1 << " " << mv2 << " " << pos1 << " " << pos2 << " " << exact <<  " " << x << endl;
    if(a[mv1] > x && x > a[mv2]) return;
    if(a[mv1] < x && x < a[mv2]) return;

    int new_x;
    if(a[mv1] < x) new_x = max(a[mv1], a[mv2]);
    else new_x = min(a[mv1], a[mv2]);

    int new_exact = (a[mv1] == new_x) ? 0 : 1;
    
    int new_pos1 = (a[mv1] == new_x) ? mv1 : pos1;
    int new_pos2 = (a[mv2] == new_x) ? mv2 : pos2;

    adj.push_back({new_pos1, new_pos2, new_exact, abs(x - new_x)});
    //build_edges(new_pos1, new_pos2, new_exact);
    //cout << pos1 << " " << pos2 << " " << exact << " -> " << new_pos1 << " " << new_pos2 << " " << new_exact << " " << abs(x - new_x) << endl;
}

void build_edges(int pos1, int pos2, bool exact, vector<array<ll, 4>> &adj){
    if(pos1 == pos2) return;

    auto &solved = dp[pos1][pos2][exact];
    if(solved) return;

    solved = true;

    int x = !exact ? a[pos1] : a[pos2];
    bool e1 = (x == a[pos1]), e2 = (x == a[pos2]);
    vector<int> v1, v2;

    if(e1){
        v1.push_back(pos1 + 1);
        if(pos1) v1.push_back(pos1 - 1);
    }
    else{
        v1.push_back(pos1 + 1);
        v1.push_back(pos1);
    }

    if(e2){
        v2.push_back(pos2 - 1);
        if(pos2 != n - 1) v2.push_back(pos2 + 1);
    }
    else{
        v2.push_back(pos2 - 1);
        v2.push_back(pos2);
    }

    move_dp(v1[0], v2[0], pos1, pos2, exact, x, adj);
    if(v2.size() == 2) move_dp(v1[0], v2[1], pos1, pos2, exact, x, adj);
    if(v1.size() == 2) move_dp(v1[1], v2[0], pos1, pos2, exact, x, adj);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i];

    vector<int> v;
    v.push_back(a[0]);

    for(int i = 1; i < n - 1; ++i){
        if(v.back() <= a[i] && a[i] <= a[i + 1])
            continue;
        if(v.back() >= a[i] && a[i] >= a[i + 1])
            continue;
        v.push_back(a[i]);
    }
    v.push_back(a[n - 1]);

    n = v.size();
    for(int i = 0; i < n; ++i)
        a[i] = v[i];

    //build_edges(0, n - 1, 0);
    ll ans = dijkstra(0, n - 1, 0);

    if(ans == INF) cout << "NO\n";
    else cout << ans << "\n";
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 876 KB Output isn't correct
2 Incorrect 2 ms 2284 KB Output isn't correct
3 Incorrect 7 ms 12268 KB Output isn't correct
4 Incorrect 48 ms 82924 KB Output isn't correct
5 Incorrect 124 ms 215916 KB Output isn't correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 640 KB Output isn't correct
2 Incorrect 1 ms 620 KB Output isn't correct
3 Incorrect 1 ms 1260 KB Output isn't correct
4 Incorrect 1 ms 876 KB Output isn't correct
5 Incorrect 2 ms 3180 KB Output isn't correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1004 KB Output isn't correct
2 Incorrect 2 ms 2668 KB Output isn't correct
3 Incorrect 8 ms 12268 KB Output isn't correct
4 Incorrect 44 ms 76268 KB Output isn't correct
5 Incorrect 43 ms 75756 KB Output isn't correct
6 Incorrect 78 ms 138348 KB Output isn't correct
7 Incorrect 78 ms 130796 KB Output isn't correct
8 Incorrect 116 ms 195436 KB Output isn't correct
9 Incorrect 115 ms 199276 KB Output isn't correct
10 Incorrect 112 ms 194796 KB Output isn't correct