Submission #1040191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040191		Math4Life2020	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	1089 ms	2284 KiB

skyscraper

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

int main() {
	ll N,M; cin >> N >> M;
    ll B[M],P[M];
    bool found[M];
    ll val[M];
    vector<pii> doges[N];
    for (ll i=0;i<M;i++) {
        found[i]=0;
        val[i]=1e18;
        cin >> B[i] >> P[i];
        doges[B[i]].push_back({i,P[i]});
    }
    val[0]=0;
    while(1) {
        ll mv = 1e17; ll ctr = -1;
        for (ll i=0;i<M;i++) {
            if (val[i]<mv && !found[i]) {
                mv = val[i]; ctr = i;
            }
        }
        if (ctr==-1) {
            cout << "-1"; exit(0);
        } else if (ctr==1) {
            cout << val[1]; exit(0);
        } else {
            ll i = ctr;
            for (ll t=(-(B[i]/P[i]+2));t<(((N-B[i])/P[i])+2);t++) {
                if ((B[i]+t*P[i])>=0 && (B[i]+t*P[i])<N) {
                    for (pii p0: doges[(B[i]+t*P[i])]) {
                        val[p0.first]=min(val[p0.first],mv+(ll)abs(t));
                    }
                }
            }
            found[i]=1;
        }
    }
}

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