# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
236100 | 2020-05-31T08:08:53 Z | thtsshz_bgwrswh | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 327 ms | 262148 KB |
#pragma GCC optimize("Ofast") #include<stdio.h> #include<vector> #include<queue> #include<set> #include<utility> #include<algorithm> using namespace std; int pos[30005],power[30005],dis[30005]; vector<pair<int,int>> g[30005]; set<int> s[30005]; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; int main(){ int i,j,n,m; scanf("%d%d",&n,&m); for(i=0;i<m;i++){ scanf("%d%d",&pos[i],&power[i]); // s[pos[i]].insert(power[i]); } for(i=0;i<m;i++){ for(j=pos[i]+power[i];j<n;j+=power[i]){ // if(s[j].count(power[i])) // break; //printf("%d\n",j); g[pos[i]].emplace_back(j,(j-pos[i])/power[i]); } for(j=pos[i]-power[i];j>=0;j-=power[i]){ // if(s[j].count(power[i])) // break; g[pos[i]].emplace_back(j,(pos[i]-j)/power[i]); } // break; } for(i=0;i<n;i++) dis[i]=1000000000; dis[pos[0]]=0; pq.push({0,pos[0]}); while(pq.size()){ auto v=pq.top().second; pq.pop(); for(auto x:g[v]){ if(dis[v]+x.second<dis[x.first]){ dis[x.first]=dis[v]+x.second; pq.push({dis[x.first],x.first}); } } } if(dis[pos[1]]==1000000000) puts("-1"); else printf("%d\n",dis[pos[1]]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2432 KB | Output is correct |
2 | Correct | 6 ms | 2432 KB | Output is correct |
3 | Correct | 6 ms | 2432 KB | Output is correct |
4 | Correct | 6 ms | 2432 KB | Output is correct |
5 | Correct | 6 ms | 2432 KB | Output is correct |
6 | Correct | 6 ms | 2432 KB | Output is correct |
7 | Correct | 6 ms | 2560 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2432 KB | Output is correct |
2 | Correct | 6 ms | 2432 KB | Output is correct |
3 | Correct | 6 ms | 2432 KB | Output is correct |
4 | Correct | 6 ms | 2432 KB | Output is correct |
5 | Correct | 6 ms | 2432 KB | Output is correct |
6 | Correct | 6 ms | 2432 KB | Output is correct |
7 | Correct | 6 ms | 2432 KB | Output is correct |
8 | Correct | 6 ms | 2432 KB | Output is correct |
9 | Correct | 6 ms | 2432 KB | Output is correct |
10 | Correct | 6 ms | 2432 KB | Output is correct |
11 | Correct | 6 ms | 2560 KB | Output is correct |
12 | Correct | 9 ms | 4596 KB | Output is correct |
13 | Correct | 9 ms | 4596 KB | Output is correct |
14 | Correct | 6 ms | 2560 KB | Output is correct |
15 | Correct | 6 ms | 2560 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2432 KB | Output is correct |
2 | Correct | 6 ms | 2432 KB | Output is correct |
3 | Correct | 6 ms | 2432 KB | Output is correct |
4 | Correct | 6 ms | 2412 KB | Output is correct |
5 | Correct | 6 ms | 2432 KB | Output is correct |
6 | Correct | 6 ms | 2432 KB | Output is correct |
7 | Correct | 6 ms | 2432 KB | Output is correct |
8 | Correct | 6 ms | 2432 KB | Output is correct |
9 | Correct | 6 ms | 2432 KB | Output is correct |
10 | Correct | 6 ms | 2432 KB | Output is correct |
11 | Correct | 6 ms | 2560 KB | Output is correct |
12 | Correct | 9 ms | 4596 KB | Output is correct |
13 | Correct | 9 ms | 4724 KB | Output is correct |
14 | Correct | 7 ms | 2560 KB | Output is correct |
15 | Correct | 6 ms | 2560 KB | Output is correct |
16 | Correct | 6 ms | 2432 KB | Output is correct |
17 | Correct | 7 ms | 2688 KB | Output is correct |
18 | Correct | 6 ms | 2560 KB | Output is correct |
19 | Correct | 6 ms | 2432 KB | Output is correct |
20 | Correct | 59 ms | 34552 KB | Output is correct |
21 | Correct | 7 ms | 2432 KB | Output is correct |
22 | Correct | 6 ms | 2560 KB | Output is correct |
23 | Correct | 6 ms | 2560 KB | Output is correct |
24 | Correct | 7 ms | 2688 KB | Output is correct |
25 | Correct | 7 ms | 2560 KB | Output is correct |
26 | Correct | 64 ms | 35548 KB | Output is correct |
27 | Correct | 61 ms | 35532 KB | Output is correct |
28 | Correct | 7 ms | 2688 KB | Output is correct |
29 | Correct | 8 ms | 3328 KB | Output is correct |
30 | Correct | 7 ms | 2816 KB | Output is correct |
31 | Correct | 7 ms | 2944 KB | Output is correct |
32 | Correct | 7 ms | 2816 KB | Output is correct |
33 | Correct | 10 ms | 3968 KB | Output is correct |
34 | Correct | 10 ms | 3968 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2432 KB | Output is correct |
2 | Correct | 10 ms | 2432 KB | Output is correct |
3 | Correct | 6 ms | 2432 KB | Output is correct |
4 | Correct | 5 ms | 2432 KB | Output is correct |
5 | Correct | 6 ms | 2432 KB | Output is correct |
6 | Correct | 6 ms | 2432 KB | Output is correct |
7 | Correct | 6 ms | 2432 KB | Output is correct |
8 | Correct | 6 ms | 2432 KB | Output is correct |
9 | Correct | 6 ms | 2432 KB | Output is correct |
10 | Correct | 6 ms | 2432 KB | Output is correct |
11 | Correct | 6 ms | 2560 KB | Output is correct |
12 | Correct | 10 ms | 4724 KB | Output is correct |
13 | Correct | 9 ms | 4596 KB | Output is correct |
14 | Correct | 6 ms | 2560 KB | Output is correct |
15 | Correct | 6 ms | 2560 KB | Output is correct |
16 | Correct | 6 ms | 2560 KB | Output is correct |
17 | Correct | 7 ms | 2688 KB | Output is correct |
18 | Correct | 6 ms | 2560 KB | Output is correct |
19 | Correct | 6 ms | 2560 KB | Output is correct |
20 | Correct | 59 ms | 34552 KB | Output is correct |
21 | Correct | 6 ms | 2432 KB | Output is correct |
22 | Correct | 7 ms | 2560 KB | Output is correct |
23 | Correct | 6 ms | 2560 KB | Output is correct |
24 | Correct | 7 ms | 2688 KB | Output is correct |
25 | Correct | 7 ms | 2560 KB | Output is correct |
26 | Correct | 66 ms | 35532 KB | Output is correct |
27 | Correct | 61 ms | 35536 KB | Output is correct |
28 | Correct | 7 ms | 2688 KB | Output is correct |
29 | Correct | 9 ms | 3328 KB | Output is correct |
30 | Correct | 7 ms | 2816 KB | Output is correct |
31 | Correct | 7 ms | 2944 KB | Output is correct |
32 | Correct | 7 ms | 2816 KB | Output is correct |
33 | Correct | 10 ms | 3968 KB | Output is correct |
34 | Correct | 10 ms | 3968 KB | Output is correct |
35 | Correct | 16 ms | 4480 KB | Output is correct |
36 | Correct | 8 ms | 2688 KB | Output is correct |
37 | Correct | 18 ms | 6016 KB | Output is correct |
38 | Correct | 20 ms | 5632 KB | Output is correct |
39 | Correct | 20 ms | 5760 KB | Output is correct |
40 | Correct | 20 ms | 5632 KB | Output is correct |
41 | Correct | 20 ms | 5504 KB | Output is correct |
42 | Runtime error | 327 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
43 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2432 KB | Output is correct |
2 | Correct | 6 ms | 2432 KB | Output is correct |
3 | Correct | 6 ms | 2432 KB | Output is correct |
4 | Correct | 6 ms | 2432 KB | Output is correct |
5 | Correct | 6 ms | 2432 KB | Output is correct |
6 | Correct | 6 ms | 2432 KB | Output is correct |
7 | Correct | 6 ms | 2432 KB | Output is correct |
8 | Correct | 6 ms | 2304 KB | Output is correct |
9 | Correct | 6 ms | 2432 KB | Output is correct |
10 | Correct | 6 ms | 2432 KB | Output is correct |
11 | Correct | 7 ms | 2608 KB | Output is correct |
12 | Correct | 9 ms | 4596 KB | Output is correct |
13 | Correct | 9 ms | 4596 KB | Output is correct |
14 | Correct | 6 ms | 2560 KB | Output is correct |
15 | Correct | 6 ms | 2560 KB | Output is correct |
16 | Correct | 7 ms | 2560 KB | Output is correct |
17 | Correct | 7 ms | 2816 KB | Output is correct |
18 | Correct | 6 ms | 2560 KB | Output is correct |
19 | Correct | 6 ms | 2560 KB | Output is correct |
20 | Correct | 59 ms | 34552 KB | Output is correct |
21 | Correct | 6 ms | 2432 KB | Output is correct |
22 | Correct | 6 ms | 2560 KB | Output is correct |
23 | Correct | 6 ms | 2432 KB | Output is correct |
24 | Correct | 7 ms | 2688 KB | Output is correct |
25 | Correct | 7 ms | 2560 KB | Output is correct |
26 | Correct | 64 ms | 35544 KB | Output is correct |
27 | Correct | 61 ms | 35420 KB | Output is correct |
28 | Correct | 7 ms | 2688 KB | Output is correct |
29 | Correct | 8 ms | 3328 KB | Output is correct |
30 | Correct | 7 ms | 2816 KB | Output is correct |
31 | Correct | 7 ms | 2944 KB | Output is correct |
32 | Correct | 7 ms | 2816 KB | Output is correct |
33 | Correct | 10 ms | 3968 KB | Output is correct |
34 | Correct | 11 ms | 3968 KB | Output is correct |
35 | Correct | 16 ms | 4480 KB | Output is correct |
36 | Correct | 8 ms | 2688 KB | Output is correct |
37 | Correct | 17 ms | 6016 KB | Output is correct |
38 | Correct | 19 ms | 5504 KB | Output is correct |
39 | Correct | 20 ms | 5760 KB | Output is correct |
40 | Correct | 20 ms | 5632 KB | Output is correct |
41 | Correct | 20 ms | 5504 KB | Output is correct |
42 | Runtime error | 321 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
43 | Halted | 0 ms | 0 KB | - |