Submission #1195289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195289		Sarvar	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	0 ms	328 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18;

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

    int N, M;
    cin >> N >> M;
    vector<int> B(M), P(M);
    for(int i = 0; i < M; i++){
        cin >> B[i] >> P[i];
    }

    // Birgina binoga nechta doge joylashganini saqlaymiz
    vector<vector<int>> doges_at(N);
    for(int j = 0; j < M; j++){
        doges_at[B[j]].push_back(j);
    }

    // dist[j] = doge j ga xabar yetib borishi uchun kerak bo'lgan eng kam sakrashlar
    vector<ll> dist(M, INF);
    dist[0] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    pq.emplace(0, 0);

    while(!pq.empty()){
        auto [d, i] = pq.top(); pq.pop();
        if(d > dist[i]) continue;
        if(i == 1) break;              // doge 1 ga yetdik
        int p = P[i], b0 = B[i];

        // Oldinga sakrashlar: b0 + k*p
        for(ll k = 1, b = b0 + p; b < N; k++, b += p){
            for(int j: doges_at[b]){
                ll nd = d + k;
                if(nd < dist[j]){
                    dist[j] = nd;
                    pq.emplace(nd, j);
                }
            }
        }
        // Orqaga sakrashlar: b0 - k*p
        for(ll k = 1, b = b0 - p; b >= 0; k++, b -= p){
            for(int j: doges_at[b]){
                ll nd = d + k;
                if(nd < dist[j]){
                    dist[j] = nd;
                    pq.emplace(nd, j);
                }
            }
        }
    }

    ll ans = dist[1];
    cout << (ans == INF ? -1 : ans) << "\n";
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43