Submission #820169

#	Time	Username	Problem	Language	Result	Execution time	Memory
820169		lprochniak	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	1108 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define MAX 30009
#define pb push_back
#define st first
#define nd second
int n,m;
int p[MAX];
struct Node{
    int v;
    int waga;
};
vector<Node> edges[MAX];
int wyn[MAX];
void dijkstra(int s){
    priority_queue<pair<int,int>> q;
    q.push({0,s});

    while(!q.empty()){
        pair<int,int> t = q.top();
        q.pop();
        t.st = -t.st;
        for(auto x:edges[t.nd]){
            if(t.st+x.waga<wyn[x.v]){
                wyn[x.v] = t.st + x.waga;
                q.push({-wyn[x.v],x.v});
            }
        }
    }
}
int main(){
    cin>>n>>m;
    memset(p,0,sizeof p);
    for(int i=0;i<m;i++){
        int b,pwr;
        cin>>b>>pwr;
        p[b] = pwr;
    }
    for(int i=0;i<n;i++){
        if(p[i] == 0) continue;
        int idx = i-p[i];
        int ile = 1;
        while(idx>=0){
            edges[i].pb({idx,ile});
            idx-=p[i],ile++;
        }
        idx = i+p[i];
        ile = 1;
        while(idx<n){
            edges[i].pb({idx,ile});
            idx+=p[i],ile++;
        }
    }
    for(int i=1;i<n;i++){
        wyn[i] = 1000000000;
    }
    dijkstra(0);
    if(wyn[1] == INT_MAX){
        cout<<"-1\n";
    } else
        cout<<wyn[1]<<"\n";
    return 0;
}

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