oj.uz

Submission #336693

# Submission time Handle Problem Language Result Execution time Memory
336693 2020-12-16T12:30:03 Z Sorting Climbers (RMI18_climbers) C++17
0 / 100
 329 ms 524292 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);

int n, a[N];
ll dist[N][N][2];
bool dp[N][N][2];
vector<array<ll, 4>> adj[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});

    while(!pq.empty()){
        auto [d, pos1, pos2, exact] = pq.top();
        pq.pop();

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

        for(auto [pos1_to, pos2_to, exact_to, cost]: adj[pos1][pos2][exact]){
            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){
    //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[pos1][pos2][exact].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){
    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);
    if(v2.size() == 2) move_dp(v1[0], v2[1], pos1, pos2, exact,x);
    if(v1.size() == 2) move_dp(v1[1], v2[0], pos1, pos2, exact, x);
}

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

# Verdict Execution time Memory Grader output
1 Runtime error 329 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 278 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 287 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 283 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 283 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 282 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 286 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 287 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 286 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 294 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 286 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 289 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 296 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 286 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 291 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 283 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 298 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 288 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 296 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 287 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)