Submission #695243

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
695243	2023-02-04T20:13:54 Z	NeroZein	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	128 ms	65044 KB

skyscraper

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2003; 
const int M = 30004; 

int n, m;
int b[M];
int p[M];
int g[N][N];

inline void minSelf(int& x, int y) {
	x = min(x, y); 
}

int cost[N];
inline void dij() {
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; 
	for (int i = 0; i < n; ++i) {
		cost[i] = 1e15;
	}
	cost[b[0]] = 0;
	pq.emplace(0, b[0]);
	while (!pq.empty()) {
		auto src = pq.top(); 
		pq.pop();
		if (src.second == b[1]) {
			cout << src.first << '\n';
			exit(0);
		}
		if (src.first != cost[src.second]) {
			continue; 
		}
		for (int i = 0; i < n; ++i) {
			if (src.first + g[src.second][i] < cost[i]) {
				cost[i] = src.first + g[src.second][i];
				pq.emplace(cost[i], i); 
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			g[i][j] = 1e15;
		}
	}
	for (int i = 0; i < m; ++i) {
		cin >> b[i] >> p[i];
		for (int j = 1; j < n; ++j) {
			int l = b[i] - j * p[i];
			int r = b[i] + j * p[i];
			if (r < n) {
				minSelf(g[b[i]][r], j);
			}
			if (l >= 0) {
				minSelf(g[b[i]][l], j);
			}
		}
	}
	dij();
	cout << -1 << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	360 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	480 KB	Output is correct
9	Correct	1 ms	472 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct
11	Correct	1 ms	852 KB	Output is correct
12	Correct	1 ms	852 KB	Output is correct
13	Correct	1 ms	724 KB	Output is correct
14	Correct	1 ms	852 KB	Output is correct
15	Correct	2 ms	724 KB	Output is correct

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	472 KB	Output is correct
10	Correct	1 ms	736 KB	Output is correct
11	Correct	2 ms	852 KB	Output is correct
12	Correct	1 ms	852 KB	Output is correct
13	Correct	2 ms	852 KB	Output is correct
14	Correct	1 ms	724 KB	Output is correct
15	Correct	1 ms	852 KB	Output is correct
16	Correct	1 ms	1364 KB	Output is correct
17	Correct	6 ms	7636 KB	Output is correct
18	Correct	18 ms	27716 KB	Output is correct
19	Correct	19 ms	31612 KB	Output is correct
20	Correct	26 ms	31708 KB	Output is correct
21	Correct	3 ms	3028 KB	Output is correct
22	Correct	15 ms	28276 KB	Output is correct
23	Correct	19 ms	25416 KB	Output is correct
24	Correct	26 ms	30164 KB	Output is correct
25	Correct	22 ms	31748 KB	Output is correct
26	Correct	24 ms	31712 KB	Output is correct
27	Correct	25 ms	31720 KB	Output is correct
28	Correct	29 ms	31744 KB	Output is correct
29	Correct	23 ms	31972 KB	Output is correct
30	Correct	21 ms	31912 KB	Output is correct
31	Correct	20 ms	31932 KB	Output is correct
32	Correct	23 ms	31884 KB	Output is correct
33	Correct	28 ms	31956 KB	Output is correct
34	Correct	23 ms	31956 KB	Output is correct

Subtask #4
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	352 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	596 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct
11	Correct	1 ms	852 KB	Output is correct
12	Correct	2 ms	748 KB	Output is correct
13	Correct	1 ms	852 KB	Output is correct
14	Correct	1 ms	852 KB	Output is correct
15	Correct	1 ms	852 KB	Output is correct
16	Correct	1 ms	1364 KB	Output is correct
17	Correct	7 ms	7636 KB	Output is correct
18	Correct	14 ms	27732 KB	Output is correct
19	Correct	20 ms	31700 KB	Output is correct
20	Correct	27 ms	31708 KB	Output is correct
21	Correct	3 ms	3028 KB	Output is correct
22	Correct	15 ms	28272 KB	Output is correct
23	Correct	17 ms	25412 KB	Output is correct
24	Correct	21 ms	30148 KB	Output is correct
25	Correct	20 ms	31732 KB	Output is correct
26	Correct	25 ms	31700 KB	Output is correct
27	Correct	22 ms	31660 KB	Output is correct
28	Correct	24 ms	31712 KB	Output is correct
29	Correct	20 ms	31956 KB	Output is correct
30	Correct	26 ms	31904 KB	Output is correct
31	Correct	21 ms	31844 KB	Output is correct
32	Correct	21 ms	31852 KB	Output is correct
33	Correct	25 ms	31924 KB	Output is correct
34	Correct	26 ms	31976 KB	Output is correct
35	Correct	65 ms	22616 KB	Output is correct
36	Correct	15 ms	14036 KB	Output is correct
37	Correct	75 ms	31124 KB	Output is correct
38	Correct	93 ms	32312 KB	Output is correct
39	Correct	128 ms	32120 KB	Output is correct
40	Correct	124 ms	32172 KB	Output is correct
41	Correct	98 ms	32316 KB	Output is correct
42	Correct	92 ms	32180 KB	Output is correct
43	Correct	99 ms	32076 KB	Output is correct
44	Correct	95 ms	32180 KB	Output is correct
45	Correct	95 ms	32348 KB	Output is correct
46	Correct	127 ms	32336 KB	Output is correct

Subtask #5
0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	724 KB	Output is correct
11	Correct	1 ms	852 KB	Output is correct
12	Correct	1 ms	852 KB	Output is correct
13	Correct	1 ms	724 KB	Output is correct
14	Correct	2 ms	852 KB	Output is correct
15	Correct	1 ms	724 KB	Output is correct
16	Correct	1 ms	1364 KB	Output is correct
17	Correct	6 ms	7708 KB	Output is correct
18	Correct	20 ms	27660 KB	Output is correct
19	Correct	15 ms	31696 KB	Output is correct
20	Correct	25 ms	31708 KB	Output is correct
21	Correct	2 ms	3028 KB	Output is correct
22	Correct	15 ms	28268 KB	Output is correct
23	Correct	16 ms	25428 KB	Output is correct
24	Correct	29 ms	30144 KB	Output is correct
25	Correct	21 ms	31772 KB	Output is correct
26	Correct	23 ms	31700 KB	Output is correct
27	Correct	23 ms	31700 KB	Output is correct
28	Correct	23 ms	31704 KB	Output is correct
29	Correct	20 ms	31956 KB	Output is correct
30	Correct	18 ms	31864 KB	Output is correct
31	Correct	20 ms	31828 KB	Output is correct
32	Correct	26 ms	31880 KB	Output is correct
33	Correct	26 ms	31968 KB	Output is correct
34	Correct	22 ms	31960 KB	Output is correct
35	Correct	60 ms	22664 KB	Output is correct
36	Correct	13 ms	14036 KB	Output is correct
37	Correct	60 ms	31180 KB	Output is correct
38	Correct	86 ms	32284 KB	Output is correct
39	Correct	115 ms	32100 KB	Output is correct
40	Correct	96 ms	32156 KB	Output is correct
41	Correct	81 ms	32284 KB	Output is correct
42	Correct	95 ms	32132 KB	Output is correct
43	Correct	87 ms	32132 KB	Output is correct
44	Correct	88 ms	32140 KB	Output is correct
45	Correct	84 ms	32380 KB	Output is correct
46	Correct	81 ms	32344 KB	Output is correct
47	Runtime error	46 ms	65044 KB	Execution killed with signal 11
48	Halted	0 ms	0 KB	-

Submission #695243

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