Submission #978062

#	Time	Username	Problem	Language	Result	Execution time	Memory
978062		nnin	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	411 ms	262144 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
 
int N, M, B[30005], P[30005];
vector<pii> adj[30005];
int mindis[30005];
set<int> dog[30005];
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>N>>M;
    for(int i=0;i<M;i++) {
        cin>>B[i]>>P[i];
        dog[B[i]].insert(-P[i]);
    }
    for(int i=0;i<N;i++) {
        vector<bool> done(N, 0);
        for(int pp:dog[i]) {
            int p = -pp;
            for(int j=1;i-(j*p)>=0;j++) if(!done[i-(j*p)]) {adj[i].push_back({i-(j*p), j}); done[i-(j*p)]=1;}
            for(int j=1;i+(j*p)<N;j++) if(!done[i+(j*p)]) {adj[i].push_back({i+(j*p), j}); done[i+(j*p)]=1;}
        }
        mindis[i] = 2e9;
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, B[0]});
    mindis[B[0]] = 0;
    while(!pq.empty()) {
        auto [dis, u] = pq.top();
        pq.pop();
        if(mindis[u]!=dis) continue;
        for(auto [v, w]:adj[u]) {
            if(mindis[v]>dis+w) {
                mindis[v] = dis+w;
                pq.push({mindis[v], v});
            }
        }
    }
    if(mindis[B[1]]==2e9) cout<<-1;
    else cout<<mindis[B[1]];
}

/*
5 3
0 2
1 1
4 1
*/

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