Submission #794739

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
794739	2023-07-26T21:12:29 Z	bane	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1000 ms	4560 KB

skyscraper

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

void solve(){
	int n, m;
	cin >> n >> m;
	vector<pair<int,int>>monsters(m);
	vector<vector<int>>pos(n);
	for (int i = 0; i < m; i++){
		int b, p;
		cin >> b >> p;
		pos[b].push_back(p);
		monsters[i] = {b,p};
	}
	vector<long long>dp(n, (long long)1e18);
	dp[monsters[0].first] = 0;
	priority_queue<pair<long long,int>>pq;
	pq.push({0,monsters[0].first});
	while(!pq.empty()){
		long long dst = -pq.top().first;
		int b = pq.top().second;
		pq.pop();
		//node + pow * x = mn
		if (dp[b] != dst)continue;
		if (b == monsters[1].first){
			cout << dst << endl;
			return ;
		}
		for (auto p : pos[b]){
			for (int i = 1; i <= n / p; i++){
				int right = b + i * p;
				int left = b - i * p;
				if (left >= 0){
					if (dp[left] > dst + i){
						dp[left] = dst + i;
						pq.push({-dst-i,left});
					}
				}  

				if (right <= n - 1){
					if (dp[right] > dst + i){
						dp[right] = dst + i;
						pq.push({-dst-i,right});
					}
				}
			}
		}
	}
	cout << - 1 << endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	25 ms	524 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	2 ms	596 KB	Output is correct
30	Correct	1 ms	596 KB	Output is correct
31	Correct	1 ms	596 KB	Output is correct
32	Correct	1 ms	468 KB	Output is correct
33	Correct	2 ms	596 KB	Output is correct
34	Correct	2 ms	724 KB	Output is correct

Subtask #4
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	24 ms	524 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	2 ms	596 KB	Output is correct
30	Correct	1 ms	596 KB	Output is correct
31	Correct	2 ms	596 KB	Output is correct
32	Correct	1 ms	596 KB	Output is correct
33	Correct	3 ms	596 KB	Output is correct
34	Correct	2 ms	724 KB	Output is correct
35	Correct	5 ms	852 KB	Output is correct
36	Correct	1 ms	468 KB	Output is correct
37	Correct	4 ms	852 KB	Output is correct
38	Correct	6 ms	980 KB	Output is correct
39	Correct	5 ms	852 KB	Output is correct
40	Correct	6 ms	980 KB	Output is correct
41	Correct	7 ms	1068 KB	Output is correct
42	Correct	3 ms	740 KB	Output is correct
43	Correct	4 ms	876 KB	Output is correct
44	Correct	353 ms	1088 KB	Output is correct
45	Correct	7 ms	1228 KB	Output is correct
46	Correct	7 ms	1292 KB	Output is correct

Subtask #5
0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	24 ms	524 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	2 ms	596 KB	Output is correct
30	Correct	1 ms	596 KB	Output is correct
31	Correct	1 ms	596 KB	Output is correct
32	Correct	1 ms	596 KB	Output is correct
33	Correct	2 ms	648 KB	Output is correct
34	Correct	2 ms	736 KB	Output is correct
35	Correct	5 ms	864 KB	Output is correct
36	Correct	1 ms	468 KB	Output is correct
37	Correct	4 ms	852 KB	Output is correct
38	Correct	8 ms	1052 KB	Output is correct
39	Correct	7 ms	852 KB	Output is correct
40	Correct	5 ms	980 KB	Output is correct
41	Correct	6 ms	980 KB	Output is correct
42	Correct	4 ms	852 KB	Output is correct
43	Correct	3 ms	852 KB	Output is correct
44	Correct	352 ms	980 KB	Output is correct
45	Correct	7 ms	1240 KB	Output is correct
46	Correct	7 ms	1236 KB	Output is correct
47	Correct	7 ms	2636 KB	Output is correct
48	Correct	5 ms	1828 KB	Output is correct
49	Correct	5 ms	1872 KB	Output is correct
50	Correct	6 ms	1776 KB	Output is correct
51	Correct	13 ms	4560 KB	Output is correct
52	Correct	14 ms	3576 KB	Output is correct
53	Correct	7 ms	2728 KB	Output is correct
54	Correct	2 ms	1624 KB	Output is correct
55	Correct	2 ms	1624 KB	Output is correct
56	Execution timed out	1080 ms	3288 KB	Time limit exceeded
57	Halted	0 ms	0 KB	-

Submission #794739

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