Submission #1041290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041290		Math4Life2020	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1054 ms	2988 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 K = floor(sqrt(N+0.001));
    ll B[M],P[M];
    bool found[N];
    //ll val[M];
    ll val[N];
    vector<pii> doges[N];
    for (ll i=0;i<M;i++) {
        //val[i]=1e18;
        cin >> B[i] >> P[i];
        doges[B[i]].push_back({i,P[i]});
    }
    for (ll i=0;i<N;i++) {
        val[i]=1e18;
        found[i]=0;
    }
    val[B[0]]=0;
    while(1) {
        ll mv = 1e17; ll ctr = -1;
        for (ll i=0;i<N;i++) {
            if (val[i]<mv && !found[i]) {
                mv = val[i]; ctr = i;
            }
        }
        if (ctr==-1) {
            cout << "-1"; exit(0);
        } else if (ctr==B[1]) {
            cout << val[B[1]]; exit(0);
        } else {
            for (pii x0: doges[ctr]) {
                ll i = x0.first;
                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) {
                        val[(B[i]+t*P[i])]=min(val[(B[i]+t*P[i])],mv+(ll)abs(t));
                    }
                }
            }
        }
        found[ctr]=1;
    }
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:9:8: warning: unused variable 'K' [-Wunused-variable]
    9 |     ll K = floor(sqrt(N+0.001));
      |        ^

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