Submission #1233770

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

skyscraper

// tle
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
// #define F first 
// #define S second


signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<int> S(M), P(M); // doge start, doge power
    vector<vector<int>> B(N); // building -> doge inside
    FOR(i, M) {
        cin >> S[i] >> P[i];
        B[S[i]].push_back(i);
    }
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // jumps, building
    vector<int> vis(N, 1e9);
    pq.push({0,S[0]}); 
    while(pq.size()) {
        auto [j, u] = pq.top();
        pq.pop();
        if (vis[u] <= j) continue;
        if (u == S[1]) {cout << j; break;}
        vis[u] = j;
        for(int d: B[u]) {
            for(int m = -(u/P[d]); m <= (N-u-1)/P[d]; m++) {
                // if (u+m*P[d] < 0 || u+m*P[d] >= N) continue;
                pq.push({j+abs(m), u+m*P[d]});
            }
        }
    }
}

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