Submission #695233

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
695233	2023-02-04T20:08:13 Z	NeroZein	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	18 ms	16172 KB

skyscraper

/*
 *    author: NeroZein
 *    created: 04.02.2023 22:58:06
*/
#include <bits/stdc++.h>
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	7 ms	15956 KB	Output is correct
2	Correct	7 ms	15956 KB	Output is correct
3	Correct	7 ms	16032 KB	Output is correct
4	Correct	6 ms	15956 KB	Output is correct
5	Correct	7 ms	15956 KB	Output is correct
6	Correct	6 ms	15956 KB	Output is correct
7	Correct	6 ms	15920 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	16028 KB	Output is correct
2	Correct	7 ms	16008 KB	Output is correct
3	Correct	6 ms	15956 KB	Output is correct
4	Correct	7 ms	15956 KB	Output is correct
5	Correct	6 ms	15956 KB	Output is correct
6	Correct	6 ms	16012 KB	Output is correct
7	Correct	7 ms	15956 KB	Output is correct
8	Correct	6 ms	16012 KB	Output is correct
9	Correct	6 ms	16012 KB	Output is correct
10	Correct	8 ms	15956 KB	Output is correct
11	Correct	7 ms	15928 KB	Output is correct
12	Correct	7 ms	15956 KB	Output is correct
13	Correct	7 ms	15956 KB	Output is correct
14	Correct	7 ms	15956 KB	Output is correct
15	Correct	8 ms	15964 KB	Output is correct

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	15972 KB	Output is correct
2	Correct	6 ms	15956 KB	Output is correct
3	Correct	6 ms	15956 KB	Output is correct
4	Correct	7 ms	15956 KB	Output is correct
5	Correct	9 ms	15956 KB	Output is correct
6	Correct	7 ms	15956 KB	Output is correct
7	Correct	8 ms	15956 KB	Output is correct
8	Correct	7 ms	15956 KB	Output is correct
9	Correct	7 ms	15956 KB	Output is correct
10	Correct	6 ms	15956 KB	Output is correct
11	Correct	7 ms	15956 KB	Output is correct
12	Correct	7 ms	15992 KB	Output is correct
13	Correct	7 ms	15956 KB	Output is correct
14	Correct	7 ms	15968 KB	Output is correct
15	Correct	7 ms	16056 KB	Output is correct
16	Correct	6 ms	15956 KB	Output is correct
17	Correct	9 ms	15956 KB	Output is correct
18	Correct	9 ms	16032 KB	Output is correct
19	Correct	9 ms	15956 KB	Output is correct
20	Correct	16 ms	16084 KB	Output is correct
21	Correct	8 ms	15956 KB	Output is correct
22	Correct	9 ms	15956 KB	Output is correct
23	Correct	14 ms	16032 KB	Output is correct
24	Correct	16 ms	15956 KB	Output is correct
25	Correct	13 ms	15956 KB	Output is correct
26	Correct	18 ms	15956 KB	Output is correct
27	Correct	16 ms	16064 KB	Output is correct
28	Correct	15 ms	16052 KB	Output is correct
29	Correct	12 ms	16104 KB	Output is correct
30	Correct	11 ms	16096 KB	Output is correct
31	Correct	12 ms	16100 KB	Output is correct
32	Correct	12 ms	16116 KB	Output is correct
33	Correct	18 ms	16048 KB	Output is correct
34	Correct	17 ms	16084 KB	Output is correct

Subtask #4
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	15956 KB	Output is correct
2	Correct	6 ms	15956 KB	Output is correct
3	Correct	6 ms	15956 KB	Output is correct
4	Correct	6 ms	15956 KB	Output is correct
5	Correct	7 ms	15952 KB	Output is correct
6	Correct	6 ms	15956 KB	Output is correct
7	Correct	7 ms	15956 KB	Output is correct
8	Correct	7 ms	15956 KB	Output is correct
9	Correct	7 ms	15956 KB	Output is correct
10	Correct	6 ms	15956 KB	Output is correct
11	Correct	8 ms	15956 KB	Output is correct
12	Correct	7 ms	15956 KB	Output is correct
13	Correct	7 ms	15956 KB	Output is correct
14	Correct	7 ms	15956 KB	Output is correct
15	Correct	8 ms	15956 KB	Output is correct
16	Correct	7 ms	15956 KB	Output is correct
17	Correct	9 ms	16084 KB	Output is correct
18	Correct	9 ms	15956 KB	Output is correct
19	Correct	8 ms	16032 KB	Output is correct
20	Correct	17 ms	15956 KB	Output is correct
21	Correct	10 ms	15956 KB	Output is correct
22	Correct	10 ms	15956 KB	Output is correct
23	Correct	11 ms	15956 KB	Output is correct
24	Correct	16 ms	15956 KB	Output is correct
25	Correct	13 ms	16044 KB	Output is correct
26	Correct	15 ms	15956 KB	Output is correct
27	Correct	16 ms	15964 KB	Output is correct
28	Correct	15 ms	16044 KB	Output is correct
29	Correct	13 ms	16160 KB	Output is correct
30	Correct	11 ms	16084 KB	Output is correct
31	Correct	12 ms	16084 KB	Output is correct
32	Correct	12 ms	16028 KB	Output is correct
33	Correct	16 ms	16172 KB	Output is correct
34	Correct	16 ms	16084 KB	Output is correct
35	Incorrect	11 ms	15984 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	16012 KB	Output is correct
2	Correct	6 ms	15988 KB	Output is correct
3	Correct	6 ms	15956 KB	Output is correct
4	Correct	7 ms	15956 KB	Output is correct
5	Correct	7 ms	16008 KB	Output is correct
6	Correct	6 ms	15956 KB	Output is correct
7	Correct	6 ms	15956 KB	Output is correct
8	Correct	8 ms	15956 KB	Output is correct
9	Correct	6 ms	15956 KB	Output is correct
10	Correct	6 ms	15956 KB	Output is correct
11	Correct	8 ms	16016 KB	Output is correct
12	Correct	9 ms	15956 KB	Output is correct
13	Correct	7 ms	15992 KB	Output is correct
14	Correct	8 ms	15956 KB	Output is correct
15	Correct	10 ms	15956 KB	Output is correct
16	Correct	6 ms	15956 KB	Output is correct
17	Correct	9 ms	15956 KB	Output is correct
18	Correct	9 ms	15956 KB	Output is correct
19	Correct	8 ms	15956 KB	Output is correct
20	Correct	17 ms	16040 KB	Output is correct
21	Correct	7 ms	15956 KB	Output is correct
22	Correct	8 ms	15956 KB	Output is correct
23	Correct	11 ms	15972 KB	Output is correct
24	Correct	17 ms	15956 KB	Output is correct
25	Correct	14 ms	16044 KB	Output is correct
26	Correct	15 ms	15956 KB	Output is correct
27	Correct	15 ms	15944 KB	Output is correct
28	Correct	16 ms	16040 KB	Output is correct
29	Correct	13 ms	16116 KB	Output is correct
30	Correct	11 ms	16084 KB	Output is correct
31	Correct	12 ms	16084 KB	Output is correct
32	Correct	11 ms	16084 KB	Output is correct
33	Correct	16 ms	16084 KB	Output is correct
34	Correct	18 ms	16168 KB	Output is correct
35	Incorrect	10 ms	15956 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Submission #695233

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