# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
977521 | Amaarsaa | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 595 ms | 7632 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
ll D[30005];
vector < ll > v[30005];
int main() {
// freopen("moocast.in", "r", stdin);
// freopen("moocast.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
ll t, n, m, ans, s, sum,dist, x, y, r, p, i, j;
cin >> m >> n;
priority_queue < pair < ll, ll >, vector < pair < ll, ll >> , greater < pair < ll, ll >> > pq;
ll a[n + 2], b[n + 2];
for (i = 0; i < n; i ++) {
cin >> a[i] >> b[i];
v[a[i]].push_back(b[i]);
}
for (i = 0; i <= m; i ++) D[i] = 1e18;
D[a[0]] = 0;
pq.push({0, a[0]});
while(!pq.empty()) {
x = pq.top().first;
y = pq.top().second;
pq.pop();
if ( x != D[y]) continue;
for ( ll X : v[y]) {
s = y - X;
dist = 1;
while ( s >= 0) {
if ( D[s] > D[y] + dist) {
D[s] = D[y] + dist;
pq.push({D[s], s});
}
dist ++;
s -= X;
}
s = y + X;
dist = 1;
while ( s < m) {
if ( D[s] > D[y] + dist) {
D[s] = D[y] + dist;
pq.push({D[s], s});
}
dist ++;
s += X;
}
}
}
if ( D[a[1]] == 1e18) cout << -1 << endl;
else cout << D[a[1]] << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |