답안 #40149 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40149	2018-01-28T13:51:56 Z	Abelyan	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	797 ms	18120 KB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define sc second
#define fr first
#define pr pair<int,int>
#define _mp make_pair

const int N=2006,M=30006,INF=1000000007;
int g[N][N],d[N];
priority_queue <pr> p;
pr a[M];
bool col[N];


int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i=0;i<m;i++){
	    int b,p;
	    scanf("%d%d",&b,&p);
	    a[i]=_mp(b,p);
	}
	for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            g[i][j]=INF;
        }
	}
	for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (i%a[j].sc==a[j].fr%a[j].sc){
                g[a[j].fr][i]=min(g[a[j].fr][i],abs(a[j].fr-i)/a[j].sc);
            }
        }
	}
	for (int i=0;i<n;i++){
        d[i]=INF;
	}
	d[a[0].fr]=0;
	p.push(_mp(0,a[0].fr));
	while (!p.empty()){
        int v;
        do{
           v=p.top().sc;
           p.pop();
        }while(col[v] && !p.empty());
        if (col[v] && p.empty()) break;
        col[v]=true;
        for (int i=0;i<n;i++){
            if (g[v][i]!=INF && !col[i] && d[i]>d[v]+g[v][i]){
                d[i]=d[v]+g[v][i];
                p.push(_mp(-d[i],i));
            }
        }
	}
	if (d[a[1].fr]==INF){
        cout<<-1<<endl;
        return 0;
	}
	cout<<d[a[1].fr]<<endl;
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:19:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
skyscraper.cpp:22:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d",&b,&p);
                         ^

Subtask #1
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	17980 KB	Output is correct
2	Correct	17980 KB	Output is correct
3	Correct	17980 KB	Output is correct
4	Correct	17980 KB	Output is correct
5	Correct	17980 KB	Output is correct
6	Correct	17980 KB	Output is correct
7	Correct	17980 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	17980 KB	Output is correct
2	Correct	0 ms	17980 KB	Output is correct
3	Correct	0 ms	17980 KB	Output is correct
4	Correct	0 ms	17980 KB	Output is correct
5	Correct	0 ms	17980 KB	Output is correct
6	Correct	0 ms	17980 KB	Output is correct
7	Correct	0 ms	17980 KB	Output is correct
8	Correct	0 ms	17980 KB	Output is correct
9	Correct	0 ms	17980 KB	Output is correct
10	Correct	1 ms	17980 KB	Output is correct
11	Correct	3 ms	17980 KB	Output is correct
12	Correct	5 ms	17980 KB	Output is correct
13	Correct	5 ms	17980 KB	Output is correct
14	Correct	3 ms	17980 KB	Output is correct
15	Correct	3 ms	17980 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	17980 KB	Output is correct
2	Correct	0 ms	17980 KB	Output is correct
3	Correct	0 ms	17980 KB	Output is correct
4	Correct	0 ms	17980 KB	Output is correct
5	Correct	0 ms	17980 KB	Output is correct
6	Correct	0 ms	17980 KB	Output is correct
7	Correct	0 ms	17980 KB	Output is correct
8	Correct	0 ms	17980 KB	Output is correct
9	Correct	0 ms	17980 KB	Output is correct
10	Correct	0 ms	17980 KB	Output is correct
11	Correct	3 ms	17980 KB	Output is correct
12	Correct	1 ms	17980 KB	Output is correct
13	Correct	3 ms	17980 KB	Output is correct
14	Correct	2 ms	17980 KB	Output is correct
15	Correct	3 ms	17980 KB	Output is correct
16	Correct	0 ms	17980 KB	Output is correct
17	Correct	14 ms	17980 KB	Output is correct
18	Correct	22 ms	17980 KB	Output is correct
19	Correct	18 ms	17980 KB	Output is correct
20	Correct	100 ms	17980 KB	Output is correct
21	Correct	7 ms	17980 KB	Output is correct
22	Correct	9 ms	17980 KB	Output is correct
23	Correct	24 ms	17980 KB	Output is correct
24	Correct	30 ms	17980 KB	Output is correct
25	Correct	50 ms	18120 KB	Output is correct
26	Correct	66 ms	17980 KB	Output is correct
27	Correct	64 ms	17980 KB	Output is correct
28	Correct	40 ms	17980 KB	Output is correct
29	Correct	24 ms	18120 KB	Output is correct
30	Correct	13 ms	18120 KB	Output is correct
31	Correct	15 ms	18120 KB	Output is correct
32	Correct	12 ms	18120 KB	Output is correct
33	Correct	43 ms	18120 KB	Output is correct
34	Correct	44 ms	18120 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	17980 KB	Output is correct
2	Correct	0 ms	17980 KB	Output is correct
3	Correct	0 ms	17980 KB	Output is correct
4	Correct	0 ms	17980 KB	Output is correct
5	Correct	0 ms	17980 KB	Output is correct
6	Correct	0 ms	17980 KB	Output is correct
7	Correct	0 ms	17980 KB	Output is correct
8	Correct	0 ms	17980 KB	Output is correct
9	Correct	0 ms	17980 KB	Output is correct
10	Correct	1 ms	17980 KB	Output is correct
11	Correct	2 ms	17980 KB	Output is correct
12	Correct	3 ms	17980 KB	Output is correct
13	Correct	3 ms	17980 KB	Output is correct
14	Correct	2 ms	17980 KB	Output is correct
15	Correct	3 ms	17980 KB	Output is correct
16	Correct	3 ms	17980 KB	Output is correct
17	Correct	11 ms	17980 KB	Output is correct
18	Correct	17 ms	17980 KB	Output is correct
19	Correct	15 ms	17980 KB	Output is correct
20	Correct	78 ms	17980 KB	Output is correct
21	Correct	6 ms	17980 KB	Output is correct
22	Correct	22 ms	17980 KB	Output is correct
23	Correct	20 ms	17980 KB	Output is correct
24	Correct	43 ms	17980 KB	Output is correct
25	Correct	37 ms	18120 KB	Output is correct
26	Correct	55 ms	17980 KB	Output is correct
27	Correct	57 ms	17980 KB	Output is correct
28	Correct	50 ms	17980 KB	Output is correct
29	Correct	18 ms	18120 KB	Output is correct
30	Correct	13 ms	18120 KB	Output is correct
31	Correct	23 ms	18120 KB	Output is correct
32	Correct	19 ms	18120 KB	Output is correct
33	Correct	46 ms	18120 KB	Output is correct
34	Correct	41 ms	18120 KB	Output is correct
35	Correct	285 ms	18120 KB	Output is correct
36	Correct	47 ms	17980 KB	Output is correct
37	Correct	314 ms	18120 KB	Output is correct
38	Correct	520 ms	18120 KB	Output is correct
39	Correct	526 ms	18120 KB	Output is correct
40	Correct	505 ms	18120 KB	Output is correct
41	Correct	474 ms	18120 KB	Output is correct
42	Correct	726 ms	17980 KB	Output is correct
43	Correct	768 ms	17980 KB	Output is correct
44	Correct	797 ms	17980 KB	Output is correct
45	Correct	484 ms	18120 KB	Output is correct
46	Correct	471 ms	18120 KB	Output is correct

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	17980 KB	Output is correct
2	Correct	0 ms	17980 KB	Output is correct
3	Correct	0 ms	17980 KB	Output is correct
4	Correct	0 ms	17980 KB	Output is correct
5	Correct	0 ms	17980 KB	Output is correct
6	Correct	0 ms	17980 KB	Output is correct
7	Correct	0 ms	17980 KB	Output is correct
8	Correct	0 ms	17980 KB	Output is correct
9	Correct	0 ms	17980 KB	Output is correct
10	Correct	1 ms	17980 KB	Output is correct
11	Correct	0 ms	17980 KB	Output is correct
12	Correct	3 ms	17980 KB	Output is correct
13	Correct	3 ms	17980 KB	Output is correct
14	Correct	2 ms	17980 KB	Output is correct
15	Correct	2 ms	17980 KB	Output is correct
16	Correct	2 ms	17980 KB	Output is correct
17	Correct	13 ms	17980 KB	Output is correct
18	Correct	17 ms	17980 KB	Output is correct
19	Correct	14 ms	17980 KB	Output is correct
20	Correct	77 ms	17980 KB	Output is correct
21	Correct	3 ms	17980 KB	Output is correct
22	Correct	12 ms	17980 KB	Output is correct
23	Correct	20 ms	17980 KB	Output is correct
24	Correct	36 ms	17980 KB	Output is correct
25	Correct	35 ms	18120 KB	Output is correct
26	Correct	51 ms	17980 KB	Output is correct
27	Correct	54 ms	17980 KB	Output is correct
28	Correct	41 ms	17980 KB	Output is correct
29	Correct	26 ms	18120 KB	Output is correct
30	Correct	16 ms	18120 KB	Output is correct
31	Correct	16 ms	18120 KB	Output is correct
32	Correct	17 ms	18120 KB	Output is correct
33	Correct	40 ms	18120 KB	Output is correct
34	Correct	43 ms	18120 KB	Output is correct
35	Correct	304 ms	18120 KB	Output is correct
36	Correct	42 ms	17980 KB	Output is correct
37	Correct	318 ms	18120 KB	Output is correct
38	Correct	509 ms	18120 KB	Output is correct
39	Correct	488 ms	18120 KB	Output is correct
40	Correct	487 ms	18120 KB	Output is correct
41	Correct	495 ms	18120 KB	Output is correct
42	Correct	744 ms	17980 KB	Output is correct
43	Correct	738 ms	17980 KB	Output is correct
44	Correct	777 ms	17980 KB	Output is correct
45	Correct	469 ms	18120 KB	Output is correct
46	Correct	497 ms	18120 KB	Output is correct
47	Runtime error	22 ms	17980 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Halted	0 ms	0 KB	-

답안 #40149

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 21.0 / 21.0

Subtask #5 0 / 43.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
14.0 / 14.0

Subtask #4
21.0 / 21.0

Subtask #5
0 / 43.0