#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 30000;
int n, m, b[maxn], p[maxn], dist[maxn];
set<int> st[maxn];
vector<int> adj[maxn], cost[maxn];
void addedge(int u, int v, int c) {
adj[u].push_back(v);
cost[u].push_back(c);
}
int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
freopen("in", "r", stdin);
#endif
int ans = 0;
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++) {
scanf("%d %d", &b[i], &p[i]);
st[b[i]].insert(p[i]);
}
for(int pos = 0; pos < n; pos++) {
for(int p : st[pos]) {
for(int i = 1; ; i++) {
int nxt = pos + i * p;
if(nxt < n) {
addedge(pos, nxt, i);
if(st[nxt].find(p) != st[nxt].end()) break;
} else break;
}
for(int i = 1; ; i++) {
int nxt = pos - i * p;
if(nxt >= 0) {
addedge(pos, nxt, i);
if(st[nxt].find(p) != st[nxt].end()) break;
} else break;
}
}
}
priority_queue<ii, vector<ii>, greater<ii> > q;
memset(dist, 63, sizeof dist);
q.push({dist[b[0]] = 0, b[0]});
while(!q.empty()) {
ii x = q.top(); q.pop();
int u = x.second, w = x.first;
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i], c = cost[u][i];
if(dist[v] > w + c) {
dist[v] = w + c;
q.push({dist[v], v});
}
}
}
if(dist[b[1]] >= 1e8) puts("-1");
else cout << dist[b[1]] << endl;
}
Compilation message
skyscraper.cpp: In function 'int main(int, const char**)':
skyscraper.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
^
skyscraper.cpp:22:6: warning: unused variable 'ans' [-Wunused-variable]
int ans = 0;
^
skyscraper.cpp:23:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
^
skyscraper.cpp:26:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &b[i], &p[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3192 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3296 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3428 KB |
Output is correct |
| 4 |
Correct |
4 ms |
3428 KB |
Output is correct |
| 5 |
Correct |
4 ms |
3428 KB |
Output is correct |
| 6 |
Correct |
4 ms |
3428 KB |
Output is correct |
| 7 |
Correct |
4 ms |
3428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
3428 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3428 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3428 KB |
Output is correct |
| 4 |
Correct |
4 ms |
3476 KB |
Output is correct |
| 5 |
Correct |
4 ms |
3476 KB |
Output is correct |
| 6 |
Correct |
4 ms |
3476 KB |
Output is correct |
| 7 |
Correct |
4 ms |
3476 KB |
Output is correct |
| 8 |
Correct |
4 ms |
3492 KB |
Output is correct |
| 9 |
Correct |
5 ms |
3492 KB |
Output is correct |
| 10 |
Correct |
4 ms |
3548 KB |
Output is correct |
| 11 |
Correct |
5 ms |
3776 KB |
Output is correct |
| 12 |
Correct |
4 ms |
3776 KB |
Output is correct |
| 13 |
Correct |
4 ms |
3776 KB |
Output is correct |
| 14 |
Correct |
5 ms |
3776 KB |
Output is correct |
| 15 |
Correct |
5 ms |
3776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3776 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3776 KB |
Output is correct |
| 3 |
Correct |
4 ms |
3776 KB |
Output is correct |
| 4 |
Correct |
4 ms |
3776 KB |
Output is correct |
| 5 |
Correct |
4 ms |
3776 KB |
Output is correct |
| 6 |
Correct |
3 ms |
3776 KB |
Output is correct |
| 7 |
Correct |
3 ms |
3776 KB |
Output is correct |
| 8 |
Correct |
3 ms |
3776 KB |
Output is correct |
| 9 |
Correct |
5 ms |
3776 KB |
Output is correct |
| 10 |
Correct |
5 ms |
3776 KB |
Output is correct |
| 11 |
Correct |
5 ms |
3776 KB |
Output is correct |
| 12 |
Correct |
4 ms |
3776 KB |
Output is correct |
| 13 |
Correct |
4 ms |
3776 KB |
Output is correct |
| 14 |
Correct |
5 ms |
3776 KB |
Output is correct |
| 15 |
Correct |
6 ms |
3776 KB |
Output is correct |
| 16 |
Correct |
5 ms |
3776 KB |
Output is correct |
| 17 |
Correct |
5 ms |
3820 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3820 KB |
Output is correct |
| 19 |
Correct |
5 ms |
3820 KB |
Output is correct |
| 20 |
Correct |
5 ms |
3820 KB |
Output is correct |
| 21 |
Correct |
5 ms |
3820 KB |
Output is correct |
| 22 |
Correct |
4 ms |
3820 KB |
Output is correct |
| 23 |
Correct |
5 ms |
3820 KB |
Output is correct |
| 24 |
Correct |
6 ms |
3820 KB |
Output is correct |
| 25 |
Correct |
6 ms |
4000 KB |
Output is correct |
| 26 |
Correct |
4 ms |
4000 KB |
Output is correct |
| 27 |
Correct |
5 ms |
4000 KB |
Output is correct |
| 28 |
Correct |
6 ms |
4036 KB |
Output is correct |
| 29 |
Correct |
7 ms |
4696 KB |
Output is correct |
| 30 |
Correct |
5 ms |
4696 KB |
Output is correct |
| 31 |
Correct |
5 ms |
4696 KB |
Output is correct |
| 32 |
Correct |
6 ms |
4696 KB |
Output is correct |
| 33 |
Correct |
10 ms |
5500 KB |
Output is correct |
| 34 |
Correct |
10 ms |
5512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5512 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5512 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5512 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 7 |
Correct |
3 ms |
5512 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 11 |
Correct |
5 ms |
5512 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 13 |
Correct |
5 ms |
5512 KB |
Output is correct |
| 14 |
Correct |
5 ms |
5512 KB |
Output is correct |
| 15 |
Correct |
5 ms |
5512 KB |
Output is correct |
| 16 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 17 |
Correct |
5 ms |
5512 KB |
Output is correct |
| 18 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 19 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 20 |
Correct |
5 ms |
5512 KB |
Output is correct |
| 21 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 22 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 23 |
Correct |
5 ms |
5512 KB |
Output is correct |
| 24 |
Correct |
6 ms |
5512 KB |
Output is correct |
| 25 |
Correct |
5 ms |
5512 KB |
Output is correct |
| 26 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 27 |
Correct |
4 ms |
5512 KB |
Output is correct |
| 28 |
Correct |
5 ms |
5512 KB |
Output is correct |
| 29 |
Correct |
7 ms |
5512 KB |
Output is correct |
| 30 |
Correct |
6 ms |
5512 KB |
Output is correct |
| 31 |
Correct |
5 ms |
5512 KB |
Output is correct |
| 32 |
Correct |
5 ms |
5512 KB |
Output is correct |
| 33 |
Correct |
10 ms |
5572 KB |
Output is correct |
| 34 |
Correct |
11 ms |
5656 KB |
Output is correct |
| 35 |
Correct |
26 ms |
6560 KB |
Output is correct |
| 36 |
Correct |
7 ms |
6560 KB |
Output is correct |
| 37 |
Correct |
29 ms |
7460 KB |
Output is correct |
| 38 |
Correct |
35 ms |
8004 KB |
Output is correct |
| 39 |
Correct |
33 ms |
8268 KB |
Output is correct |
| 40 |
Correct |
33 ms |
8532 KB |
Output is correct |
| 41 |
Correct |
35 ms |
8796 KB |
Output is correct |
| 42 |
Correct |
9 ms |
8796 KB |
Output is correct |
| 43 |
Correct |
11 ms |
8796 KB |
Output is correct |
| 44 |
Correct |
10 ms |
8796 KB |
Output is correct |
| 45 |
Correct |
44 ms |
12756 KB |
Output is correct |
| 46 |
Correct |
38 ms |
12972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12972 KB |
Output is correct |
| 2 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12972 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12972 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12972 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12972 KB |
Output is correct |
| 7 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 8 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 9 |
Correct |
3 ms |
12972 KB |
Output is correct |
| 10 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 11 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 12 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 13 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 14 |
Correct |
5 ms |
12972 KB |
Output is correct |
| 15 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 16 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 17 |
Correct |
5 ms |
12972 KB |
Output is correct |
| 18 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 19 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 20 |
Correct |
5 ms |
12972 KB |
Output is correct |
| 21 |
Correct |
5 ms |
12972 KB |
Output is correct |
| 22 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 23 |
Correct |
5 ms |
12972 KB |
Output is correct |
| 24 |
Correct |
7 ms |
12972 KB |
Output is correct |
| 25 |
Correct |
5 ms |
12972 KB |
Output is correct |
| 26 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 27 |
Correct |
4 ms |
12972 KB |
Output is correct |
| 28 |
Correct |
7 ms |
12972 KB |
Output is correct |
| 29 |
Correct |
7 ms |
12972 KB |
Output is correct |
| 30 |
Correct |
5 ms |
12972 KB |
Output is correct |
| 31 |
Correct |
5 ms |
12972 KB |
Output is correct |
| 32 |
Correct |
5 ms |
12972 KB |
Output is correct |
| 33 |
Correct |
11 ms |
12972 KB |
Output is correct |
| 34 |
Correct |
11 ms |
12972 KB |
Output is correct |
| 35 |
Correct |
24 ms |
12972 KB |
Output is correct |
| 36 |
Correct |
7 ms |
12972 KB |
Output is correct |
| 37 |
Correct |
29 ms |
12972 KB |
Output is correct |
| 38 |
Correct |
32 ms |
12972 KB |
Output is correct |
| 39 |
Correct |
32 ms |
12972 KB |
Output is correct |
| 40 |
Correct |
33 ms |
12972 KB |
Output is correct |
| 41 |
Correct |
33 ms |
12972 KB |
Output is correct |
| 42 |
Correct |
9 ms |
12972 KB |
Output is correct |
| 43 |
Correct |
9 ms |
12972 KB |
Output is correct |
| 44 |
Correct |
10 ms |
12972 KB |
Output is correct |
| 45 |
Correct |
37 ms |
15420 KB |
Output is correct |
| 46 |
Correct |
36 ms |
15632 KB |
Output is correct |
| 47 |
Correct |
73 ms |
20192 KB |
Output is correct |
| 48 |
Correct |
26 ms |
20192 KB |
Output is correct |
| 49 |
Correct |
22 ms |
20192 KB |
Output is correct |
| 50 |
Correct |
18 ms |
20192 KB |
Output is correct |
| 51 |
Correct |
60 ms |
20192 KB |
Output is correct |
| 52 |
Correct |
64 ms |
20192 KB |
Output is correct |
| 53 |
Correct |
27 ms |
20192 KB |
Output is correct |
| 54 |
Correct |
6 ms |
20192 KB |
Output is correct |
| 55 |
Correct |
7 ms |
20192 KB |
Output is correct |
| 56 |
Correct |
26 ms |
20192 KB |
Output is correct |
| 57 |
Correct |
54 ms |
20404 KB |
Output is correct |
| 58 |
Correct |
13 ms |
20404 KB |
Output is correct |
| 59 |
Correct |
14 ms |
20404 KB |
Output is correct |
| 60 |
Correct |
16 ms |
20404 KB |
Output is correct |
| 61 |
Correct |
18 ms |
20404 KB |
Output is correct |
| 62 |
Correct |
35 ms |
20404 KB |
Output is correct |
| 63 |
Correct |
96 ms |
38036 KB |
Output is correct |
| 64 |
Correct |
121 ms |
41448 KB |
Output is correct |
| 65 |
Correct |
133 ms |
51228 KB |
Output is correct |
| 66 |
Correct |
299 ms |
78724 KB |
Output is correct |
| 67 |
Correct |
307 ms |
78924 KB |
Output is correct |
