# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
207091 | 2020-03-06T11:38:28 Z | Sa1loum | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 547 ms | 262148 KB |
#include <bits/stdc++.h> using namespace std; #define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define mem(a,b) memset(a, b, sizeof(a)) #define F first #define S second #define Si size() #define pb(x) push_back(x) typedef double D; typedef long long ll; typedef long double ld; const int MOD=(int)1e9+7,MAX=(int)1e6+10; ll n,m,b[MAX],p[MAX],vis[MAX]; vector <pair<ll,ll> > v[MAX]; int main() { scanf("%lld%lld",&n,&m); ll s,e; for (int i=0;i<m;i++) { scanf("%lld%lld",&b[i],&p[i]); ll d=0; if (i==0) s=b[i]; if (i==1) e=b[i]; for (int j=b[i],k=b[i];;j+=p[i],k-=p[i]) { bool flag=0; if (0<=j && j<n) { flag=1; if (j!=b[i]) { v[b[i]].push_back({j,d}); } } if (0<=k && k<n) { flag=1; if (k!=b[i]) { v[b[i]].push_back({k,d}); } } d++; if (!flag) break; } } priority_queue <pair<ll,ll>> pq; pq.push({0,s}); while (!pq.empty()) { ll x=pq.top().S; ll w=-pq.top().F; pq.pop(); if (vis[x]) continue; vis[x]=1; if (x==e) {printf("%lld\n",w); return 0;} for (auto it:v[x]) { if (vis[it.F]) continue; pq.push({-w-it.S,it.F}); } } puts("-1\n"); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23800 KB | Output is correct |
2 | Correct | 19 ms | 23672 KB | Output is correct |
3 | Correct | 20 ms | 23800 KB | Output is correct |
4 | Correct | 20 ms | 23856 KB | Output is correct |
5 | Correct | 23 ms | 23804 KB | Output is correct |
6 | Correct | 19 ms | 23800 KB | Output is correct |
7 | Correct | 20 ms | 23912 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23800 KB | Output is correct |
2 | Correct | 19 ms | 23800 KB | Output is correct |
3 | Correct | 20 ms | 23800 KB | Output is correct |
4 | Correct | 20 ms | 23848 KB | Output is correct |
5 | Correct | 20 ms | 23800 KB | Output is correct |
6 | Correct | 19 ms | 23800 KB | Output is correct |
7 | Correct | 19 ms | 23800 KB | Output is correct |
8 | Correct | 20 ms | 23928 KB | Output is correct |
9 | Correct | 20 ms | 23800 KB | Output is correct |
10 | Correct | 20 ms | 23928 KB | Output is correct |
11 | Correct | 20 ms | 24056 KB | Output is correct |
12 | Correct | 26 ms | 28132 KB | Output is correct |
13 | Correct | 27 ms | 28132 KB | Output is correct |
14 | Correct | 20 ms | 24056 KB | Output is correct |
15 | Correct | 20 ms | 24056 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 23800 KB | Output is correct |
2 | Correct | 19 ms | 23800 KB | Output is correct |
3 | Correct | 21 ms | 23800 KB | Output is correct |
4 | Correct | 20 ms | 23800 KB | Output is correct |
5 | Correct | 20 ms | 23800 KB | Output is correct |
6 | Correct | 19 ms | 23800 KB | Output is correct |
7 | Correct | 20 ms | 23800 KB | Output is correct |
8 | Correct | 19 ms | 23800 KB | Output is correct |
9 | Correct | 20 ms | 23800 KB | Output is correct |
10 | Correct | 20 ms | 23928 KB | Output is correct |
11 | Correct | 20 ms | 24056 KB | Output is correct |
12 | Correct | 26 ms | 28132 KB | Output is correct |
13 | Correct | 26 ms | 28132 KB | Output is correct |
14 | Correct | 20 ms | 24056 KB | Output is correct |
15 | Correct | 20 ms | 24056 KB | Output is correct |
16 | Correct | 20 ms | 23928 KB | Output is correct |
17 | Correct | 21 ms | 24696 KB | Output is correct |
18 | Correct | 20 ms | 23800 KB | Output is correct |
19 | Correct | 20 ms | 23928 KB | Output is correct |
20 | Correct | 528 ms | 104528 KB | Output is correct |
21 | Correct | 21 ms | 23928 KB | Output is correct |
22 | Correct | 23 ms | 23904 KB | Output is correct |
23 | Correct | 20 ms | 23928 KB | Output is correct |
24 | Correct | 21 ms | 24312 KB | Output is correct |
25 | Correct | 20 ms | 24056 KB | Output is correct |
26 | Correct | 120 ms | 89888 KB | Output is correct |
27 | Correct | 124 ms | 89880 KB | Output is correct |
28 | Correct | 22 ms | 24312 KB | Output is correct |
29 | Correct | 31 ms | 26420 KB | Output is correct |
30 | Correct | 23 ms | 24696 KB | Output is correct |
31 | Correct | 24 ms | 25204 KB | Output is correct |
32 | Correct | 23 ms | 24696 KB | Output is correct |
33 | Correct | 45 ms | 28524 KB | Output is correct |
34 | Correct | 36 ms | 28460 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 23800 KB | Output is correct |
2 | Correct | 20 ms | 23800 KB | Output is correct |
3 | Correct | 20 ms | 23800 KB | Output is correct |
4 | Correct | 19 ms | 23800 KB | Output is correct |
5 | Correct | 20 ms | 23800 KB | Output is correct |
6 | Correct | 20 ms | 23800 KB | Output is correct |
7 | Correct | 20 ms | 23800 KB | Output is correct |
8 | Correct | 20 ms | 23800 KB | Output is correct |
9 | Correct | 20 ms | 23928 KB | Output is correct |
10 | Correct | 20 ms | 23928 KB | Output is correct |
11 | Correct | 21 ms | 24056 KB | Output is correct |
12 | Correct | 25 ms | 28132 KB | Output is correct |
13 | Correct | 27 ms | 28132 KB | Output is correct |
14 | Correct | 21 ms | 24056 KB | Output is correct |
15 | Correct | 20 ms | 24056 KB | Output is correct |
16 | Correct | 20 ms | 23928 KB | Output is correct |
17 | Correct | 22 ms | 24696 KB | Output is correct |
18 | Correct | 20 ms | 23928 KB | Output is correct |
19 | Correct | 20 ms | 23928 KB | Output is correct |
20 | Correct | 547 ms | 104528 KB | Output is correct |
21 | Correct | 20 ms | 23928 KB | Output is correct |
22 | Correct | 20 ms | 23928 KB | Output is correct |
23 | Correct | 21 ms | 24056 KB | Output is correct |
24 | Correct | 22 ms | 24312 KB | Output is correct |
25 | Correct | 21 ms | 24056 KB | Output is correct |
26 | Correct | 121 ms | 89888 KB | Output is correct |
27 | Correct | 118 ms | 89752 KB | Output is correct |
28 | Correct | 24 ms | 24312 KB | Output is correct |
29 | Correct | 33 ms | 26420 KB | Output is correct |
30 | Correct | 23 ms | 24696 KB | Output is correct |
31 | Correct | 25 ms | 25204 KB | Output is correct |
32 | Correct | 23 ms | 24696 KB | Output is correct |
33 | Correct | 45 ms | 28524 KB | Output is correct |
34 | Correct | 37 ms | 28464 KB | Output is correct |
35 | Correct | 35 ms | 28548 KB | Output is correct |
36 | Correct | 23 ms | 24440 KB | Output is correct |
37 | Correct | 38 ms | 32748 KB | Output is correct |
38 | Correct | 42 ms | 31720 KB | Output is correct |
39 | Correct | 39 ms | 29816 KB | Output is correct |
40 | Correct | 37 ms | 30196 KB | Output is correct |
41 | Correct | 44 ms | 31472 KB | Output is correct |
42 | Runtime error | 343 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
43 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 23800 KB | Output is correct |
2 | Correct | 20 ms | 23800 KB | Output is correct |
3 | Correct | 21 ms | 23800 KB | Output is correct |
4 | Correct | 20 ms | 23800 KB | Output is correct |
5 | Correct | 20 ms | 23800 KB | Output is correct |
6 | Correct | 20 ms | 23800 KB | Output is correct |
7 | Correct | 20 ms | 23800 KB | Output is correct |
8 | Correct | 21 ms | 23800 KB | Output is correct |
9 | Correct | 20 ms | 23804 KB | Output is correct |
10 | Correct | 21 ms | 23928 KB | Output is correct |
11 | Correct | 20 ms | 24056 KB | Output is correct |
12 | Correct | 27 ms | 28132 KB | Output is correct |
13 | Correct | 26 ms | 28132 KB | Output is correct |
14 | Correct | 21 ms | 24056 KB | Output is correct |
15 | Correct | 21 ms | 24056 KB | Output is correct |
16 | Correct | 21 ms | 23888 KB | Output is correct |
17 | Correct | 21 ms | 24696 KB | Output is correct |
18 | Correct | 20 ms | 23928 KB | Output is correct |
19 | Correct | 20 ms | 23928 KB | Output is correct |
20 | Correct | 547 ms | 104656 KB | Output is correct |
21 | Correct | 20 ms | 23804 KB | Output is correct |
22 | Correct | 20 ms | 24056 KB | Output is correct |
23 | Correct | 20 ms | 24056 KB | Output is correct |
24 | Correct | 22 ms | 24248 KB | Output is correct |
25 | Correct | 21 ms | 24056 KB | Output is correct |
26 | Correct | 121 ms | 89888 KB | Output is correct |
27 | Correct | 119 ms | 89752 KB | Output is correct |
28 | Correct | 23 ms | 24312 KB | Output is correct |
29 | Correct | 32 ms | 26420 KB | Output is correct |
30 | Correct | 23 ms | 24696 KB | Output is correct |
31 | Correct | 25 ms | 25204 KB | Output is correct |
32 | Correct | 22 ms | 24700 KB | Output is correct |
33 | Correct | 46 ms | 28524 KB | Output is correct |
34 | Correct | 37 ms | 28432 KB | Output is correct |
35 | Correct | 35 ms | 28676 KB | Output is correct |
36 | Correct | 21 ms | 24440 KB | Output is correct |
37 | Correct | 37 ms | 32748 KB | Output is correct |
38 | Correct | 42 ms | 31596 KB | Output is correct |
39 | Correct | 37 ms | 29756 KB | Output is correct |
40 | Correct | 36 ms | 30192 KB | Output is correct |
41 | Correct | 43 ms | 31472 KB | Output is correct |
42 | Runtime error | 309 ms | 262144 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
43 | Halted | 0 ms | 0 KB | - |