Submission #1125314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125314		njoop	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	1092 KiB

skyscraper

#include <bits/stdc++.h>
#define int short
#define pii pair<int, int>
using namespace std;

short MXN = 30000;
short n, m, dis[30001], b, p, d=174, st, en, cnt, cd, cb, cp, nd, nb, np;
vector<int> g[30001];
priority_queue<pii, vector<pii>, greater<pii>> pq;

signed main() {
    cin >> n >> m;
    for(int i=0; i<30001; i++) {
        dis[i] = 32700;
    }
    for(int i=0; i<m; i++) {
        cin >> b >> p;
        if(i == 0) st = b;
        if(i == 1) en = b;
        g[b].push_back(p);
    }
    pq.push({0, st});
    while(pq.size()) {
        cd = pq.top().first;
        cb = pq.top().second;
        pq.pop();
        if(cd > dis[cb]) continue;
        for(auto i: g[cb]) {
            for(int j=1; cb+(i*j) < n; j++) {
                nb = cb+(i*j);
                if(cd+j < dis[nb]) {
                    dis[nb] = cd+j;
                    pq.push({cd+j, nb});
                }
            }
            for(int j=1; cb-(i*j) >= 0; j++) {
                nb = cb-(i*j);
                if(cd+j < dis[nb]) {
                    dis[nb] = cd+j;
                    pq.push({cd+j, nb});
                }
            }
        }
    }
    if(dis[en] == 32700) cout << -1;
    else cout << dis[en];
    return 0;
}

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