#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define ll int
#define ss second
#define ff first
#define INF 2000000000000000
#define pb push_back
#define edge pair<ll, pair<ll,ll> > // une, number ,power
#define cost first
#define num second.first
#define pwr second.second
ll n,m,l,r,i,j,ii,jj,k,x,y,D[30001][177],s,e;
vector< edge > v[30001][177];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
for(i=1;i<=m;i++){
cin>>l>>r;
if(i==1) s=l;
if(i==2) e=l;
if(r>175)
for(j=1 ; l+r*j<n || l-r*j>=0 ; j++){
edge a;
a.num=l+r*j;
a.pwr=176;
a.cost=j;
if(a.num<n) v[l][176].pb(a);
a.num=l-r*j;
if(a.num>=0) v[l][176].pb(a);
}
else{
v[l][176].pb({0,{l,r}});
}
}
priority_queue<edge , vector< edge >, greater< edge > > q;
memset(D,-1,sizeof(D));
q.push({0,{s,176}});
while(!q.empty()){
ll une, nmbr, power;
une=q.top().cost;
nmbr=q.top().num;
power=q.top().pwr;
if(nmbr==e){
cout<<une;
return 0;
}
q.pop();
if(D[nmbr][power]!=-1);
else{
D[nmbr][power]=une;
for(edge no : v[nmbr][power]) q.push({une+no.cost,{no.num,no.pwr}});
if(power!=176){
q.push({une,{nmbr,176}});
if(nmbr+power<n) q.push({une+1,{nmbr+power,power}});
if(nmbr-power>=0) q.push({une+1,{nmbr-power,power}});
}
}
}
cout<<D[e][200];
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:65:19: warning: array subscript 200 is above array bounds of 'int [177]' [-Warray-bounds]
65 | cout<<D[e][200];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
145780 KB |
Output is correct |
2 |
Correct |
72 ms |
145720 KB |
Output is correct |
3 |
Correct |
76 ms |
145712 KB |
Output is correct |
4 |
Correct |
74 ms |
145740 KB |
Output is correct |
5 |
Correct |
74 ms |
145780 KB |
Output is correct |
6 |
Correct |
84 ms |
145692 KB |
Output is correct |
7 |
Correct |
76 ms |
145784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
145756 KB |
Output is correct |
2 |
Correct |
70 ms |
145764 KB |
Output is correct |
3 |
Correct |
69 ms |
145760 KB |
Output is correct |
4 |
Correct |
68 ms |
145784 KB |
Output is correct |
5 |
Correct |
69 ms |
145860 KB |
Output is correct |
6 |
Correct |
67 ms |
145740 KB |
Output is correct |
7 |
Correct |
71 ms |
145872 KB |
Output is correct |
8 |
Correct |
69 ms |
145728 KB |
Output is correct |
9 |
Correct |
78 ms |
145732 KB |
Output is correct |
10 |
Correct |
80 ms |
145752 KB |
Output is correct |
11 |
Correct |
81 ms |
145820 KB |
Output is correct |
12 |
Correct |
77 ms |
145712 KB |
Output is correct |
13 |
Correct |
66 ms |
145804 KB |
Output is correct |
14 |
Correct |
76 ms |
145892 KB |
Output is correct |
15 |
Correct |
73 ms |
145868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
145752 KB |
Output is correct |
2 |
Correct |
70 ms |
145780 KB |
Output is correct |
3 |
Correct |
69 ms |
145680 KB |
Output is correct |
4 |
Correct |
71 ms |
145776 KB |
Output is correct |
5 |
Correct |
75 ms |
145684 KB |
Output is correct |
6 |
Correct |
67 ms |
145704 KB |
Output is correct |
7 |
Correct |
67 ms |
145732 KB |
Output is correct |
8 |
Correct |
69 ms |
145752 KB |
Output is correct |
9 |
Correct |
78 ms |
145760 KB |
Output is correct |
10 |
Correct |
67 ms |
145796 KB |
Output is correct |
11 |
Correct |
76 ms |
145800 KB |
Output is correct |
12 |
Correct |
75 ms |
145832 KB |
Output is correct |
13 |
Correct |
72 ms |
145836 KB |
Output is correct |
14 |
Correct |
69 ms |
145852 KB |
Output is correct |
15 |
Correct |
70 ms |
145896 KB |
Output is correct |
16 |
Correct |
67 ms |
145720 KB |
Output is correct |
17 |
Correct |
69 ms |
145876 KB |
Output is correct |
18 |
Correct |
73 ms |
145760 KB |
Output is correct |
19 |
Correct |
70 ms |
145744 KB |
Output is correct |
20 |
Correct |
77 ms |
145748 KB |
Output is correct |
21 |
Correct |
68 ms |
145740 KB |
Output is correct |
22 |
Correct |
67 ms |
145804 KB |
Output is correct |
23 |
Correct |
75 ms |
145816 KB |
Output is correct |
24 |
Correct |
80 ms |
145796 KB |
Output is correct |
25 |
Correct |
69 ms |
145820 KB |
Output is correct |
26 |
Correct |
72 ms |
145832 KB |
Output is correct |
27 |
Correct |
77 ms |
145848 KB |
Output is correct |
28 |
Correct |
81 ms |
145840 KB |
Output is correct |
29 |
Correct |
88 ms |
145844 KB |
Output is correct |
30 |
Correct |
73 ms |
145796 KB |
Output is correct |
31 |
Correct |
80 ms |
145868 KB |
Output is correct |
32 |
Correct |
76 ms |
145868 KB |
Output is correct |
33 |
Correct |
119 ms |
145868 KB |
Output is correct |
34 |
Correct |
91 ms |
145924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
145680 KB |
Output is correct |
2 |
Correct |
66 ms |
145700 KB |
Output is correct |
3 |
Correct |
82 ms |
145704 KB |
Output is correct |
4 |
Correct |
75 ms |
145708 KB |
Output is correct |
5 |
Correct |
73 ms |
145748 KB |
Output is correct |
6 |
Correct |
67 ms |
145736 KB |
Output is correct |
7 |
Correct |
69 ms |
145780 KB |
Output is correct |
8 |
Correct |
67 ms |
145740 KB |
Output is correct |
9 |
Correct |
71 ms |
145736 KB |
Output is correct |
10 |
Correct |
68 ms |
145696 KB |
Output is correct |
11 |
Correct |
69 ms |
145728 KB |
Output is correct |
12 |
Correct |
66 ms |
145812 KB |
Output is correct |
13 |
Correct |
68 ms |
145868 KB |
Output is correct |
14 |
Correct |
68 ms |
145868 KB |
Output is correct |
15 |
Correct |
78 ms |
145908 KB |
Output is correct |
16 |
Correct |
74 ms |
145748 KB |
Output is correct |
17 |
Correct |
69 ms |
145816 KB |
Output is correct |
18 |
Correct |
72 ms |
145700 KB |
Output is correct |
19 |
Correct |
66 ms |
145768 KB |
Output is correct |
20 |
Correct |
72 ms |
145740 KB |
Output is correct |
21 |
Correct |
75 ms |
145788 KB |
Output is correct |
22 |
Correct |
70 ms |
145760 KB |
Output is correct |
23 |
Correct |
70 ms |
145736 KB |
Output is correct |
24 |
Correct |
67 ms |
145888 KB |
Output is correct |
25 |
Correct |
69 ms |
145704 KB |
Output is correct |
26 |
Correct |
75 ms |
145944 KB |
Output is correct |
27 |
Correct |
81 ms |
145808 KB |
Output is correct |
28 |
Correct |
70 ms |
145796 KB |
Output is correct |
29 |
Correct |
88 ms |
145824 KB |
Output is correct |
30 |
Correct |
74 ms |
145736 KB |
Output is correct |
31 |
Correct |
81 ms |
145840 KB |
Output is correct |
32 |
Correct |
89 ms |
145740 KB |
Output is correct |
33 |
Correct |
114 ms |
145836 KB |
Output is correct |
34 |
Correct |
95 ms |
145880 KB |
Output is correct |
35 |
Correct |
80 ms |
146712 KB |
Output is correct |
36 |
Correct |
73 ms |
145824 KB |
Output is correct |
37 |
Correct |
81 ms |
147720 KB |
Output is correct |
38 |
Correct |
80 ms |
147044 KB |
Output is correct |
39 |
Correct |
83 ms |
146760 KB |
Output is correct |
40 |
Correct |
100 ms |
146764 KB |
Output is correct |
41 |
Correct |
73 ms |
146920 KB |
Output is correct |
42 |
Correct |
102 ms |
146244 KB |
Output is correct |
43 |
Correct |
83 ms |
146248 KB |
Output is correct |
44 |
Correct |
117 ms |
146684 KB |
Output is correct |
45 |
Correct |
297 ms |
151900 KB |
Output is correct |
46 |
Correct |
208 ms |
151764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
74 ms |
145668 KB |
Output is correct |
2 |
Correct |
96 ms |
145740 KB |
Output is correct |
3 |
Correct |
85 ms |
145712 KB |
Output is correct |
4 |
Correct |
83 ms |
145720 KB |
Output is correct |
5 |
Correct |
76 ms |
145744 KB |
Output is correct |
6 |
Correct |
78 ms |
145740 KB |
Output is correct |
7 |
Correct |
82 ms |
145744 KB |
Output is correct |
8 |
Correct |
78 ms |
145784 KB |
Output is correct |
9 |
Correct |
85 ms |
145776 KB |
Output is correct |
10 |
Correct |
81 ms |
145808 KB |
Output is correct |
11 |
Correct |
86 ms |
145780 KB |
Output is correct |
12 |
Correct |
85 ms |
145836 KB |
Output is correct |
13 |
Correct |
76 ms |
145884 KB |
Output is correct |
14 |
Correct |
97 ms |
145892 KB |
Output is correct |
15 |
Correct |
85 ms |
145972 KB |
Output is correct |
16 |
Correct |
84 ms |
145812 KB |
Output is correct |
17 |
Correct |
81 ms |
145868 KB |
Output is correct |
18 |
Correct |
89 ms |
145824 KB |
Output is correct |
19 |
Correct |
126 ms |
145732 KB |
Output is correct |
20 |
Correct |
127 ms |
145860 KB |
Output is correct |
21 |
Correct |
76 ms |
145784 KB |
Output is correct |
22 |
Correct |
84 ms |
145764 KB |
Output is correct |
23 |
Correct |
75 ms |
145800 KB |
Output is correct |
24 |
Correct |
86 ms |
145868 KB |
Output is correct |
25 |
Correct |
85 ms |
145744 KB |
Output is correct |
26 |
Correct |
71 ms |
145800 KB |
Output is correct |
27 |
Correct |
71 ms |
145800 KB |
Output is correct |
28 |
Correct |
89 ms |
145752 KB |
Output is correct |
29 |
Correct |
108 ms |
145724 KB |
Output is correct |
30 |
Correct |
76 ms |
145796 KB |
Output is correct |
31 |
Correct |
84 ms |
145724 KB |
Output is correct |
32 |
Correct |
99 ms |
145744 KB |
Output is correct |
33 |
Correct |
221 ms |
145872 KB |
Output is correct |
34 |
Correct |
112 ms |
145936 KB |
Output is correct |
35 |
Correct |
99 ms |
146976 KB |
Output is correct |
36 |
Correct |
95 ms |
145884 KB |
Output is correct |
37 |
Correct |
85 ms |
147904 KB |
Output is correct |
38 |
Correct |
91 ms |
147276 KB |
Output is correct |
39 |
Correct |
94 ms |
146956 KB |
Output is correct |
40 |
Correct |
92 ms |
147144 KB |
Output is correct |
41 |
Correct |
81 ms |
147228 KB |
Output is correct |
42 |
Correct |
76 ms |
146472 KB |
Output is correct |
43 |
Correct |
81 ms |
146408 KB |
Output is correct |
44 |
Correct |
85 ms |
146908 KB |
Output is correct |
45 |
Correct |
265 ms |
151872 KB |
Output is correct |
46 |
Correct |
173 ms |
151784 KB |
Output is correct |
47 |
Correct |
129 ms |
153064 KB |
Output is correct |
48 |
Correct |
79 ms |
147568 KB |
Output is correct |
49 |
Correct |
96 ms |
147176 KB |
Output is correct |
50 |
Correct |
84 ms |
147032 KB |
Output is correct |
51 |
Correct |
101 ms |
149212 KB |
Output is correct |
52 |
Correct |
100 ms |
149208 KB |
Output is correct |
53 |
Correct |
80 ms |
146100 KB |
Output is correct |
54 |
Correct |
76 ms |
145724 KB |
Output is correct |
55 |
Correct |
87 ms |
145784 KB |
Output is correct |
56 |
Correct |
104 ms |
146952 KB |
Output is correct |
57 |
Correct |
74 ms |
145764 KB |
Output is correct |
58 |
Correct |
102 ms |
146740 KB |
Output is correct |
59 |
Correct |
92 ms |
146488 KB |
Output is correct |
60 |
Correct |
87 ms |
146892 KB |
Output is correct |
61 |
Correct |
82 ms |
146716 KB |
Output is correct |
62 |
Correct |
135 ms |
149312 KB |
Output is correct |
63 |
Correct |
846 ms |
192756 KB |
Output is correct |
64 |
Correct |
979 ms |
205984 KB |
Output is correct |
65 |
Execution timed out |
1090 ms |
215292 KB |
Time limit exceeded |
66 |
Halted |
0 ms |
0 KB |
- |