제출 #1275827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275827		namious	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1096 ms	3224 KiB

skyscraper

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

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];
        // اگر ورودی 1-based باشه:
        // B[i]--;
    }

    // برای هر موقعیت، سگ‌هایی که اونجا هستن
    vector<vector<int>> dogs_at_pos(n);
    for (int i = 0; i < m; i++) {
        dogs_at_pos[B[i]].push_back(i);
    }

    vector<int> dist(m, INF);
    using pii = pair<int,int>;
    priority_queue<pii, vector<pii>, greater<pii>> pq;

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

    while (!pq.empty()) {
        auto [d,u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        if (u == 1) break; // جواب پیدا شد

        int bu = B[u], pu = P[u];
        int rem = bu % pu;

        // همه‌ی موقعیت‌هایی که دوج u می‌تونه برسه
        for (int x = rem; x < n; x += pu) {
            int cost = abs(x - bu) / pu;
            // همه‌ی دوج‌هایی که سر این موقعیت هستن
            for (int v : dogs_at_pos[x]) {
                int nd = d + cost;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    pq.push({nd, v});
                }
            }
        }
    }

    if (dist[1] == INF) cout << -1 << "\n";
    else cout << dist[1] << "\n";
    return 0;
}

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