oj.uz

Submission #71782

# Submission time Handle Problem Language Result Execution time Memory
71782 2018-08-25T15:45:31 Z tamref_official_fanclub(#2249, imeimi2000) Angelic Hourglass (FXCUP3_hourglass) C++17
100 / 100
 20 ms 1380 KB 
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;int n;int dist[5][7][5001];struct node{int t3,t5,ta,d;bool operator<(const node&p)const{return d>p.d;}};const int inf=1e9;int main(){scanf("%d", &n);for(int i=0;i<=4;++i){for(int j=0;j<=6;++j){for(int k=0;k<=5000;++k){dist[i][j][k] = inf;}}}priority_queue<node>pq;dist[1][1][0]=0;pq.push({0,0,0,0});while(!pq.empty()){node x=pq.top();pq.pop();if(dist[x.t3+1][x.t5+1][x.ta]!=x.d)continue;if(x.t3==0||x.t5==0){if(dist[3-max(x.t3,0)+1][x.t5+1][x.ta]>x.d+1)pq.push({3-max(x.t3,0),x.t5,x.ta,dist[3-max(x.t3,0)+1][x.t5+1][x.ta]=x.d+1});if(dist[x.t3+1][5-max(x.t5,0)+1][x.ta]>x.d+1)pq.push({x.t3,5-max(x.t5,0),x.ta,dist[x.t3+1][5-max(x.t5,0)+1][x.ta]=x.d+1});}if(x.ta<n)if(dist[max(x.t3,0)][max(x.t5,0)][x.ta+1]>x.d)pq.push({max(x.t3,0)-1,max(x.t5,0)-1,x.ta+1,dist[max(x.t3,0)][max(x.t5,0)][x.ta+1]=x.d});}int ans=inf;for(int i=0;i<=6;++i){ans=min(ans,dist[1][i][n]);if(i<=4)ans=min(ans,dist[i][1][n]);}printf("%d\n",ans<inf?ans:-1);return 0;}

Compilation message

hourglass.cpp: In function 'int main()':
hourglass.cpp:4:159: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 using namespace std;int n;int dist[5][7][5001];struct node{int t3,t5,ta,d;bool operator<(const node&p)const{return d>p.d;}};const int inf=1e9;int main(){scanf("%d", &n);for(int i=0;i<=4;++i){for(int j=0;j<=6;++j){for(int k=0;k<=5000;++k){dist[i][j][k] = inf;}}}priority_queue<node>pq;dist[1][1][0]=0;pq.push({0,0,0,0});while(!pq.empty()){node x=pq.top();pq.pop();if(dist[x.t3+1][x.t5+1][x.ta]!=x.d)continue;if(x.t3==0||x.t5==0){if(dist[3-max(x.t3,0)+1][x.t5+1][x.ta]>x.d+1)pq.push({3-max(x.t3,0),x.t5,x.ta,dist[3-max(x.t3,0)+1][x.t5+1][x.ta]=x.d+1});if(dist[x.t3+1][5-max(x.t5,0)+1][x.ta]>x.d+1)pq.push({x.t3,5-max(x.t5,0),x.ta,dist[x.t3+1][5-max(x.t5,0)+1][x.ta]=x.d+1});}if(x.ta<n)if(dist[max(x.t3,0)][max(x.t5,0)][x.ta+1]>x.d)pq.push({max(x.t3,0)-1,max(x.t5,0)-1,x.ta+1,dist[max(x.t3,0)][max(x.t5,0)][x.ta+1]=x.d});}int ans=inf;for(int i=0;i<=6;++i){ans=min(ans,dist[1][i][n]);if(i<=4)ans=min(ans,dist[i][1][n]);}printf("%d\n",ans<inf?ans:-1);return 0;}
                                                                                                                                                          ~~~~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 4 ms 1216 KB Output is correct
3 Correct 14 ms 1216 KB Output is correct
4 Correct 20 ms 1216 KB Output is correct
5 Correct 5 ms 1216 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1252 KB Output is correct
2 Correct 2 ms 1380 KB Output is correct
3 Correct 3 ms 1380 KB Output is correct
4 Correct 2 ms 1216 KB Output is correct
5 Correct 3 ms 1216 KB Output is correct
6 Correct 3 ms 1380 KB Output is correct
7 Correct 2 ms 1380 KB Output is correct
8 Correct 3 ms 1380 KB Output is correct
9 Correct 3 ms 1380 KB Output is correct
10 Correct 3 ms 1380 KB Output is correct
11 Correct 3 ms 1380 KB Output is correct
12 Correct 3 ms 1380 KB Output is correct
13 Correct 3 ms 1380 KB Output is correct
14 Correct 3 ms 1380 KB Output is correct
15 Correct 3 ms 1380 KB Output is correct
16 Correct 2 ms 1380 KB Output is correct
17 Correct 3 ms 1380 KB Output is correct
18 Correct 2 ms 1380 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1380 KB Output is correct
2 Correct 6 ms 1380 KB Output is correct
3 Correct 11 ms 1380 KB Output is correct
4 Correct 4 ms 1380 KB Output is correct
5 Correct 4 ms 1380 KB Output is correct
6 Correct 18 ms 1380 KB Output is correct
7 Correct 16 ms 1380 KB Output is correct
8 Correct 5 ms 1380 KB Output is correct
9 Correct 3 ms 1380 KB Output is correct
10 Correct 5 ms 1380 KB Output is correct
11 Correct 3 ms 1380 KB Output is correct
12 Correct 3 ms 1380 KB Output is correct