// Need to git gud and reach 1900+
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define prev prev123
#define next next123
#define pow pow123
#define left left123
#define right right123
const int N = 30007;
const int M = 207;
const int INF = 1e9 + 7;
int a[N], b[N];
int d[N][M];
int m, n, s, f;
vector < int > lst[N];
main(){ // If you don't know what to do, check the text box at the bottom
cin >> m >> n;
for (int i = 1; i <= n; i++){
scanf("%d%d", &a[i], &b[i]);
lst[a[i] + 1].pb(b[i]);
}
s = a[1] + 1, f = a[2] + 1;
priority_queue < pair < int, pi > > pq;
pq.push(mk(0, mk(s, 0)));
memset(d, 0x3f3f3f3f, sizeof(d));
d[s][0] = 0;
while (!pq.empty()){
int w = -pq.top().fr, v = pq.top().sc.fr, pw = pq.top().sc.sc;
pq.pop();
if (d[v][pw] < w)
continue;
if (pw == 0){
for (int to : lst[v]){
if (to > 175){
int pos = v, c = 0;
while (pos + to <= m){
pos += to; c++;
if (d[pos][0] > d[v][0] + c){
d[pos][0] = d[v][0] + c;
pq.push(mk(-d[pos][0], mk(pos, 0)));
}
}
pos = v, c = 0;
while (pos - to > 0){
pos -= to; c++;
if (d[pos][0] > d[v][0] + c){
d[pos][0] = d[v][0] + c;
pq.push(mk(-d[pos][0], mk(pos, 0)));
}
}
}
else {
if (d[v][to] > d[v][0]){
d[v][to] = d[v][0];
pq.push(mk(-d[v][to], mk(v, to)));
}
}
}
}
else {
if (v + pw <= m && d[v + pw][pw] > d[v][pw] + 1){
d[v + pw][pw] = d[v][pw] + 1;
pq.push(mk(-d[v + pw][pw], mk(v + pw, pw)));
}
if (v + pw <= m && d[v + pw][0] > d[v][pw] + 1){
d[v + pw][0] = d[v][pw] + 1;
pq.push(mk(-d[v + pw][0], mk(v + pw, 0)));
}
if (v - pw > 0 && d[v - pw][pw] > d[v][pw] + 1){
d[v - pw][pw] = d[v][pw] + 1;
pq.push(mk(-d[v - pw][pw], mk(v - pw, pw)));
}
if (v - pw > 0 && d[v - pw][0] > d[v][pw] + 1){
d[v - pw][0] = d[v][pw] + 1;
pq.push(mk(-d[v - pw][0], mk(v - pw, 0)));
}
}
}
if (d[f][0] != d[0][0])
printf("%d", d[f][0]);
else
puts("-1");
}
/*
Totally not inspired by BenQ's template
Things you should do:
1. Look for stupid typos in code e.g 1 instead of -1 etc
2. Check if there is no infinite loops
3. "Measure twice, cut once"
4. Stay focused
*/
Compilation message
skyscraper.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){ // If you don't know what to do, check the text box at the bottom
^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a[i], &b[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
25336 KB |
Output is correct |
2 |
Correct |
24 ms |
25336 KB |
Output is correct |
3 |
Correct |
25 ms |
25336 KB |
Output is correct |
4 |
Correct |
25 ms |
25336 KB |
Output is correct |
5 |
Correct |
25 ms |
25412 KB |
Output is correct |
6 |
Correct |
25 ms |
25336 KB |
Output is correct |
7 |
Correct |
25 ms |
25312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
25336 KB |
Output is correct |
2 |
Correct |
24 ms |
25336 KB |
Output is correct |
3 |
Correct |
25 ms |
25336 KB |
Output is correct |
4 |
Correct |
25 ms |
25336 KB |
Output is correct |
5 |
Correct |
25 ms |
25336 KB |
Output is correct |
6 |
Correct |
26 ms |
25352 KB |
Output is correct |
7 |
Correct |
25 ms |
25336 KB |
Output is correct |
8 |
Correct |
25 ms |
25336 KB |
Output is correct |
9 |
Correct |
25 ms |
25308 KB |
Output is correct |
10 |
Correct |
25 ms |
25336 KB |
Output is correct |
11 |
Correct |
26 ms |
25336 KB |
Output is correct |
12 |
Correct |
25 ms |
25320 KB |
Output is correct |
13 |
Correct |
25 ms |
25340 KB |
Output is correct |
14 |
Correct |
26 ms |
25464 KB |
Output is correct |
15 |
Correct |
26 ms |
25464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
25336 KB |
Output is correct |
2 |
Correct |
25 ms |
25308 KB |
Output is correct |
3 |
Correct |
25 ms |
25336 KB |
Output is correct |
4 |
Correct |
25 ms |
25336 KB |
Output is correct |
5 |
Correct |
26 ms |
25328 KB |
Output is correct |
6 |
Correct |
25 ms |
25336 KB |
Output is correct |
7 |
Correct |
25 ms |
25336 KB |
Output is correct |
8 |
Correct |
25 ms |
25340 KB |
Output is correct |
9 |
Correct |
25 ms |
25336 KB |
Output is correct |
10 |
Correct |
24 ms |
25336 KB |
Output is correct |
11 |
Correct |
26 ms |
25436 KB |
Output is correct |
12 |
Correct |
25 ms |
25336 KB |
Output is correct |
13 |
Correct |
25 ms |
25336 KB |
Output is correct |
14 |
Correct |
26 ms |
25436 KB |
Output is correct |
15 |
Correct |
25 ms |
25336 KB |
Output is correct |
16 |
Correct |
25 ms |
25336 KB |
Output is correct |
17 |
Correct |
28 ms |
25336 KB |
Output is correct |
18 |
Correct |
25 ms |
25336 KB |
Output is correct |
19 |
Correct |
25 ms |
25312 KB |
Output is correct |
20 |
Correct |
26 ms |
25340 KB |
Output is correct |
21 |
Correct |
25 ms |
25336 KB |
Output is correct |
22 |
Correct |
25 ms |
25336 KB |
Output is correct |
23 |
Correct |
27 ms |
25336 KB |
Output is correct |
24 |
Correct |
27 ms |
25336 KB |
Output is correct |
25 |
Correct |
26 ms |
25464 KB |
Output is correct |
26 |
Correct |
26 ms |
25336 KB |
Output is correct |
27 |
Correct |
26 ms |
25336 KB |
Output is correct |
28 |
Correct |
27 ms |
25336 KB |
Output is correct |
29 |
Correct |
32 ms |
25336 KB |
Output is correct |
30 |
Correct |
27 ms |
25336 KB |
Output is correct |
31 |
Correct |
30 ms |
25436 KB |
Output is correct |
32 |
Correct |
28 ms |
25312 KB |
Output is correct |
33 |
Correct |
41 ms |
25464 KB |
Output is correct |
34 |
Correct |
41 ms |
25464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
25340 KB |
Output is correct |
2 |
Correct |
25 ms |
25336 KB |
Output is correct |
3 |
Correct |
25 ms |
25336 KB |
Output is correct |
4 |
Correct |
24 ms |
25336 KB |
Output is correct |
5 |
Correct |
25 ms |
25336 KB |
Output is correct |
6 |
Correct |
25 ms |
25336 KB |
Output is correct |
7 |
Correct |
25 ms |
25336 KB |
Output is correct |
8 |
Correct |
25 ms |
25336 KB |
Output is correct |
9 |
Correct |
25 ms |
25336 KB |
Output is correct |
10 |
Correct |
25 ms |
25336 KB |
Output is correct |
11 |
Correct |
26 ms |
25336 KB |
Output is correct |
12 |
Correct |
25 ms |
25336 KB |
Output is correct |
13 |
Correct |
25 ms |
25336 KB |
Output is correct |
14 |
Correct |
26 ms |
25336 KB |
Output is correct |
15 |
Correct |
26 ms |
25336 KB |
Output is correct |
16 |
Correct |
25 ms |
25336 KB |
Output is correct |
17 |
Correct |
28 ms |
25464 KB |
Output is correct |
18 |
Correct |
26 ms |
25464 KB |
Output is correct |
19 |
Correct |
26 ms |
25336 KB |
Output is correct |
20 |
Correct |
26 ms |
25464 KB |
Output is correct |
21 |
Correct |
26 ms |
25336 KB |
Output is correct |
22 |
Correct |
25 ms |
25464 KB |
Output is correct |
23 |
Correct |
25 ms |
25336 KB |
Output is correct |
24 |
Correct |
27 ms |
25340 KB |
Output is correct |
25 |
Correct |
26 ms |
25336 KB |
Output is correct |
26 |
Correct |
25 ms |
25336 KB |
Output is correct |
27 |
Correct |
26 ms |
25336 KB |
Output is correct |
28 |
Correct |
27 ms |
25464 KB |
Output is correct |
29 |
Correct |
33 ms |
25336 KB |
Output is correct |
30 |
Correct |
26 ms |
25336 KB |
Output is correct |
31 |
Correct |
30 ms |
25336 KB |
Output is correct |
32 |
Correct |
28 ms |
25464 KB |
Output is correct |
33 |
Correct |
41 ms |
25464 KB |
Output is correct |
34 |
Correct |
40 ms |
25464 KB |
Output is correct |
35 |
Correct |
42 ms |
25848 KB |
Output is correct |
36 |
Correct |
29 ms |
25592 KB |
Output is correct |
37 |
Correct |
49 ms |
25848 KB |
Output is correct |
38 |
Correct |
50 ms |
26104 KB |
Output is correct |
39 |
Correct |
49 ms |
25964 KB |
Output is correct |
40 |
Correct |
51 ms |
26104 KB |
Output is correct |
41 |
Correct |
49 ms |
25988 KB |
Output is correct |
42 |
Correct |
31 ms |
25848 KB |
Output is correct |
43 |
Correct |
31 ms |
25848 KB |
Output is correct |
44 |
Correct |
31 ms |
25848 KB |
Output is correct |
45 |
Correct |
87 ms |
26296 KB |
Output is correct |
46 |
Correct |
86 ms |
26296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
25336 KB |
Output is correct |
2 |
Correct |
25 ms |
25364 KB |
Output is correct |
3 |
Correct |
25 ms |
25336 KB |
Output is correct |
4 |
Correct |
25 ms |
25464 KB |
Output is correct |
5 |
Correct |
25 ms |
25336 KB |
Output is correct |
6 |
Correct |
25 ms |
25336 KB |
Output is correct |
7 |
Correct |
25 ms |
25340 KB |
Output is correct |
8 |
Correct |
27 ms |
25336 KB |
Output is correct |
9 |
Correct |
25 ms |
25336 KB |
Output is correct |
10 |
Correct |
25 ms |
25336 KB |
Output is correct |
11 |
Correct |
26 ms |
25464 KB |
Output is correct |
12 |
Correct |
28 ms |
25376 KB |
Output is correct |
13 |
Correct |
25 ms |
25336 KB |
Output is correct |
14 |
Correct |
26 ms |
25336 KB |
Output is correct |
15 |
Correct |
26 ms |
25436 KB |
Output is correct |
16 |
Correct |
25 ms |
25336 KB |
Output is correct |
17 |
Correct |
28 ms |
25336 KB |
Output is correct |
18 |
Correct |
25 ms |
25336 KB |
Output is correct |
19 |
Correct |
25 ms |
25336 KB |
Output is correct |
20 |
Correct |
26 ms |
25464 KB |
Output is correct |
21 |
Correct |
25 ms |
25308 KB |
Output is correct |
22 |
Correct |
25 ms |
25336 KB |
Output is correct |
23 |
Correct |
26 ms |
25336 KB |
Output is correct |
24 |
Correct |
28 ms |
25384 KB |
Output is correct |
25 |
Correct |
26 ms |
25336 KB |
Output is correct |
26 |
Correct |
26 ms |
25336 KB |
Output is correct |
27 |
Correct |
26 ms |
25308 KB |
Output is correct |
28 |
Correct |
27 ms |
25336 KB |
Output is correct |
29 |
Correct |
32 ms |
25336 KB |
Output is correct |
30 |
Correct |
27 ms |
25468 KB |
Output is correct |
31 |
Correct |
29 ms |
25208 KB |
Output is correct |
32 |
Correct |
29 ms |
25308 KB |
Output is correct |
33 |
Correct |
41 ms |
25464 KB |
Output is correct |
34 |
Correct |
41 ms |
25464 KB |
Output is correct |
35 |
Correct |
42 ms |
25848 KB |
Output is correct |
36 |
Correct |
28 ms |
25464 KB |
Output is correct |
37 |
Correct |
49 ms |
25848 KB |
Output is correct |
38 |
Correct |
49 ms |
25976 KB |
Output is correct |
39 |
Correct |
50 ms |
25976 KB |
Output is correct |
40 |
Correct |
49 ms |
25976 KB |
Output is correct |
41 |
Correct |
49 ms |
25976 KB |
Output is correct |
42 |
Correct |
31 ms |
25848 KB |
Output is correct |
43 |
Correct |
31 ms |
25848 KB |
Output is correct |
44 |
Correct |
31 ms |
25848 KB |
Output is correct |
45 |
Correct |
86 ms |
26296 KB |
Output is correct |
46 |
Correct |
87 ms |
26296 KB |
Output is correct |
47 |
Correct |
120 ms |
26424 KB |
Output is correct |
48 |
Correct |
33 ms |
25948 KB |
Output is correct |
49 |
Correct |
34 ms |
25948 KB |
Output is correct |
50 |
Correct |
31 ms |
25848 KB |
Output is correct |
51 |
Correct |
79 ms |
26680 KB |
Output is correct |
52 |
Correct |
85 ms |
26728 KB |
Output is correct |
53 |
Correct |
46 ms |
26232 KB |
Output is correct |
54 |
Correct |
26 ms |
25336 KB |
Output is correct |
55 |
Correct |
28 ms |
25336 KB |
Output is correct |
56 |
Correct |
38 ms |
26520 KB |
Output is correct |
57 |
Correct |
108 ms |
25464 KB |
Output is correct |
58 |
Correct |
36 ms |
25848 KB |
Output is correct |
59 |
Correct |
40 ms |
25848 KB |
Output is correct |
60 |
Correct |
47 ms |
25848 KB |
Output is correct |
61 |
Correct |
42 ms |
25848 KB |
Output is correct |
62 |
Correct |
72 ms |
26492 KB |
Output is correct |
63 |
Correct |
67 ms |
26756 KB |
Output is correct |
64 |
Correct |
73 ms |
26728 KB |
Output is correct |
65 |
Correct |
302 ms |
27504 KB |
Output is correct |
66 |
Correct |
940 ms |
27372 KB |
Output is correct |
67 |
Execution timed out |
1010 ms |
27500 KB |
Time limit exceeded |