Submission #695234

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
695234	2023-02-04T20:08:48 Z	NeroZein	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	28 ms	32016 KB

skyscraper

/*
 *    author: NeroZein
 *    created: 04.02.2023 22:58:06
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;

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

const int N = 2003; 

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

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

int ans;
int cost[N];
inline void dij() {
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; 
	memset(cost, 0x3f3f3f3f, sizeof cost);
	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;
	memset(g, 0x3f3f3f3f, sizeof g);
	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);
			}
		}
	}
	ans = INT_MAX;
	dij();
	cout << -1 << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	31644 KB	Output is correct
2	Correct	12 ms	31688 KB	Output is correct
3	Correct	12 ms	31664 KB	Output is correct
4	Correct	12 ms	31660 KB	Output is correct
5	Correct	12 ms	31712 KB	Output is correct
6	Correct	14 ms	31700 KB	Output is correct
7	Correct	12 ms	31700 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	31744 KB	Output is correct
2	Correct	15 ms	31700 KB	Output is correct
3	Correct	12 ms	31700 KB	Output is correct
4	Correct	14 ms	31748 KB	Output is correct
5	Correct	12 ms	31700 KB	Output is correct
6	Correct	12 ms	31700 KB	Output is correct
7	Correct	12 ms	31660 KB	Output is correct
8	Correct	12 ms	31664 KB	Output is correct
9	Correct	12 ms	31688 KB	Output is correct
10	Correct	12 ms	31700 KB	Output is correct
11	Correct	13 ms	31780 KB	Output is correct
12	Correct	14 ms	31756 KB	Output is correct
13	Correct	15 ms	31700 KB	Output is correct
14	Correct	13 ms	31700 KB	Output is correct
15	Correct	15 ms	31708 KB	Output is correct

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	31672 KB	Output is correct
2	Correct	12 ms	31700 KB	Output is correct
3	Correct	15 ms	31680 KB	Output is correct
4	Correct	12 ms	31700 KB	Output is correct
5	Correct	13 ms	31700 KB	Output is correct
6	Correct	12 ms	31692 KB	Output is correct
7	Correct	13 ms	31684 KB	Output is correct
8	Correct	13 ms	31732 KB	Output is correct
9	Correct	13 ms	31624 KB	Output is correct
10	Correct	13 ms	31672 KB	Output is correct
11	Correct	12 ms	31700 KB	Output is correct
12	Correct	13 ms	31656 KB	Output is correct
13	Correct	13 ms	31768 KB	Output is correct
14	Correct	12 ms	31700 KB	Output is correct
15	Correct	13 ms	31768 KB	Output is correct
16	Correct	13 ms	31700 KB	Output is correct
17	Correct	15 ms	31804 KB	Output is correct
18	Correct	14 ms	31748 KB	Output is correct
19	Correct	13 ms	31700 KB	Output is correct
20	Correct	22 ms	31828 KB	Output is correct
21	Correct	12 ms	31700 KB	Output is correct
22	Correct	13 ms	31700 KB	Output is correct
23	Correct	24 ms	31700 KB	Output is correct
24	Correct	20 ms	31736 KB	Output is correct
25	Correct	18 ms	31696 KB	Output is correct
26	Correct	20 ms	31744 KB	Output is correct
27	Correct	22 ms	31740 KB	Output is correct
28	Correct	24 ms	31764 KB	Output is correct
29	Correct	19 ms	31972 KB	Output is correct
30	Correct	21 ms	31828 KB	Output is correct
31	Correct	19 ms	31888 KB	Output is correct
32	Correct	19 ms	31876 KB	Output is correct
33	Correct	28 ms	31956 KB	Output is correct
34	Correct	23 ms	31940 KB	Output is correct

Subtask #4
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	31716 KB	Output is correct
2	Correct	12 ms	31676 KB	Output is correct
3	Correct	12 ms	31700 KB	Output is correct
4	Correct	18 ms	31692 KB	Output is correct
5	Correct	16 ms	31700 KB	Output is correct
6	Correct	13 ms	31700 KB	Output is correct
7	Correct	12 ms	31632 KB	Output is correct
8	Correct	13 ms	31700 KB	Output is correct
9	Correct	16 ms	31700 KB	Output is correct
10	Correct	12 ms	31732 KB	Output is correct
11	Correct	17 ms	31684 KB	Output is correct
12	Correct	12 ms	31764 KB	Output is correct
13	Correct	14 ms	31660 KB	Output is correct
14	Correct	13 ms	31700 KB	Output is correct
15	Correct	15 ms	31656 KB	Output is correct
16	Correct	12 ms	31752 KB	Output is correct
17	Correct	13 ms	31744 KB	Output is correct
18	Correct	13 ms	31740 KB	Output is correct
19	Correct	16 ms	31748 KB	Output is correct
20	Correct	23 ms	31752 KB	Output is correct
21	Correct	14 ms	31700 KB	Output is correct
22	Correct	17 ms	31656 KB	Output is correct
23	Correct	16 ms	31700 KB	Output is correct
24	Correct	19 ms	31824 KB	Output is correct
25	Correct	21 ms	31776 KB	Output is correct
26	Correct	21 ms	31700 KB	Output is correct
27	Correct	24 ms	31784 KB	Output is correct
28	Correct	21 ms	31692 KB	Output is correct
29	Correct	21 ms	31960 KB	Output is correct
30	Correct	17 ms	31828 KB	Output is correct
31	Correct	19 ms	31884 KB	Output is correct
32	Correct	16 ms	31956 KB	Output is correct
33	Correct	23 ms	32016 KB	Output is correct
34	Correct	22 ms	32012 KB	Output is correct
35	Incorrect	16 ms	31700 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	31700 KB	Output is correct
2	Correct	12 ms	31680 KB	Output is correct
3	Correct	12 ms	31700 KB	Output is correct
4	Correct	12 ms	31728 KB	Output is correct
5	Correct	12 ms	31708 KB	Output is correct
6	Correct	12 ms	31728 KB	Output is correct
7	Correct	12 ms	31636 KB	Output is correct
8	Correct	12 ms	31748 KB	Output is correct
9	Correct	14 ms	31700 KB	Output is correct
10	Correct	12 ms	31700 KB	Output is correct
11	Correct	12 ms	31700 KB	Output is correct
12	Correct	15 ms	31764 KB	Output is correct
13	Correct	12 ms	31700 KB	Output is correct
14	Correct	16 ms	31716 KB	Output is correct
15	Correct	14 ms	31688 KB	Output is correct
16	Correct	12 ms	31760 KB	Output is correct
17	Correct	16 ms	31828 KB	Output is correct
18	Correct	15 ms	31752 KB	Output is correct
19	Correct	13 ms	31700 KB	Output is correct
20	Correct	22 ms	31752 KB	Output is correct
21	Correct	12 ms	31692 KB	Output is correct
22	Correct	13 ms	31700 KB	Output is correct
23	Correct	17 ms	31712 KB	Output is correct
24	Correct	19 ms	31828 KB	Output is correct
25	Correct	19 ms	31804 KB	Output is correct
26	Correct	21 ms	31704 KB	Output is correct
27	Correct	25 ms	31700 KB	Output is correct
28	Correct	23 ms	31828 KB	Output is correct
29	Correct	20 ms	31956 KB	Output is correct
30	Correct	17 ms	31828 KB	Output is correct
31	Correct	17 ms	31980 KB	Output is correct
32	Correct	17 ms	31956 KB	Output is correct
33	Correct	22 ms	31956 KB	Output is correct
34	Correct	21 ms	32016 KB	Output is correct
35	Incorrect	15 ms	31700 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Submission #695234

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 14.0 / 14.0

Subtask #4 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
0 / 21.0

Subtask #5
0 / 43.0