답안 #39454 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39454	2018-01-15T14:54:30 Z	qoo2p5	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	213 ms	262144 KB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 123;
const ll LINF = (ll) 1e18 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int) (x).size())
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

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

const int N = 30003;

int n, m;
int b[N], p[N];
int dist[N];
bool used[N];
vector<pair<int, int>> g[N];

void run() {
	cin >> n >> m;
	rep(i, 0, m) {
		cin >> b[i] >> p[i];
	}
	
	rep(i, 0, m) {
		rep(j, 0, N) {
			int to = b[i] + (j + 1) * p[i];
			if (to >= n) {
				break;
			}
			g[b[i]].pb({to, j + 1});
		}
		rep(j, 0, N) {
			int to = b[i] - (j + 1) * p[i];
			if (to < 0) {
				break;
			}
			g[b[i]].pb({to, j + 1});
		}
	}
	
	fill(dist, dist + n, INF);
	dist[b[0]] = 0;
	priority_queue<pair<int, int>> q;
	q.push({0, b[0]});
	while (sz(q)) {
		int v = q.top().second;
		q.pop();
		if (used[v]) continue;
		used[v] = 1;
		for (auto &e : g[v]) {
			int u = e.first;
			if (mini(dist[u], dist[v] + e.second)) {
				q.push({-dist[u], u});
			}
		}
	}
	
	cout << (dist[b[1]] == INF ? -1 : dist[b[1]]) << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3260 KB	Output is correct
2	Correct	0 ms	3260 KB	Output is correct
3	Correct	0 ms	3260 KB	Output is correct
4	Correct	0 ms	3260 KB	Output is correct
5	Correct	0 ms	3260 KB	Output is correct
6	Correct	0 ms	3260 KB	Output is correct
7	Correct	0 ms	3260 KB	Output is correct
8	Correct	0 ms	3260 KB	Output is correct
9	Correct	0 ms	3260 KB	Output is correct
10	Correct	0 ms	3260 KB	Output is correct
11	Correct	0 ms	3392 KB	Output is correct
12	Correct	0 ms	6376 KB	Output is correct
13	Correct	6 ms	6388 KB	Output is correct
14	Correct	0 ms	3260 KB	Output is correct
15	Correct	0 ms	3260 KB	Output is correct
16	Correct	0 ms	3260 KB	Output is correct
17	Correct	0 ms	3528 KB	Output is correct
18	Correct	0 ms	3260 KB	Output is correct
19	Correct	0 ms	3260 KB	Output is correct
20	Correct	39 ms	35308 KB	Output is correct
21	Correct	0 ms	3260 KB	Output is correct
22	Correct	0 ms	3260 KB	Output is correct
23	Correct	0 ms	3260 KB	Output is correct
24	Correct	3 ms	3392 KB	Output is correct
25	Correct	0 ms	3392 KB	Output is correct
26	Correct	53 ms	52580 KB	Output is correct
27	Correct	46 ms	52516 KB	Output is correct
28	Correct	3 ms	3524 KB	Output is correct
29	Correct	0 ms	4144 KB	Output is correct
30	Correct	0 ms	3528 KB	Output is correct
31	Correct	0 ms	3660 KB	Output is correct
32	Correct	0 ms	3660 KB	Output is correct
33	Correct	0 ms	4736 KB	Output is correct
34	Correct	0 ms	4924 KB	Output is correct

Subtask #4
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3260 KB	Output is correct
2	Correct	0 ms	3260 KB	Output is correct
3	Correct	0 ms	3260 KB	Output is correct
4	Correct	0 ms	3260 KB	Output is correct
5	Correct	0 ms	3260 KB	Output is correct
6	Correct	0 ms	3260 KB	Output is correct
7	Correct	0 ms	3260 KB	Output is correct
8	Correct	0 ms	3260 KB	Output is correct
9	Correct	0 ms	3260 KB	Output is correct
10	Correct	0 ms	3260 KB	Output is correct
11	Correct	0 ms	3392 KB	Output is correct
12	Correct	0 ms	6376 KB	Output is correct
13	Correct	0 ms	6388 KB	Output is correct
14	Correct	0 ms	3260 KB	Output is correct
15	Correct	0 ms	3260 KB	Output is correct
16	Correct	0 ms	3260 KB	Output is correct
17	Correct	0 ms	3528 KB	Output is correct
18	Correct	0 ms	3260 KB	Output is correct
19	Correct	0 ms	3260 KB	Output is correct
20	Correct	59 ms	35308 KB	Output is correct
21	Correct	0 ms	3260 KB	Output is correct
22	Correct	0 ms	3260 KB	Output is correct
23	Correct	0 ms	3260 KB	Output is correct
24	Correct	0 ms	3392 KB	Output is correct
25	Correct	0 ms	3392 KB	Output is correct
26	Correct	39 ms	52580 KB	Output is correct
27	Correct	43 ms	52516 KB	Output is correct
28	Correct	0 ms	3524 KB	Output is correct
29	Correct	3 ms	4144 KB	Output is correct
30	Correct	0 ms	3528 KB	Output is correct
31	Correct	3 ms	3660 KB	Output is correct
32	Correct	0 ms	3660 KB	Output is correct
33	Correct	3 ms	4736 KB	Output is correct
34	Correct	0 ms	4924 KB	Output is correct
35	Correct	9 ms	4868 KB	Output is correct
36	Correct	0 ms	3536 KB	Output is correct
37	Correct	16 ms	6668 KB	Output is correct
38	Correct	19 ms	5992 KB	Output is correct
39	Correct	13 ms	6216 KB	Output is correct
40	Correct	9 ms	6100 KB	Output is correct
41	Correct	6 ms	5812 KB	Output is correct
42	Memory limit exceeded	159 ms	262144 KB	Memory limit exceeded
43	Halted	0 ms	0 KB	-

Subtask #5
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3260 KB	Output is correct
2	Correct	0 ms	3260 KB	Output is correct
3	Correct	0 ms	3260 KB	Output is correct
4	Correct	0 ms	3260 KB	Output is correct
5	Correct	0 ms	3260 KB	Output is correct
6	Correct	0 ms	3260 KB	Output is correct
7	Correct	0 ms	3260 KB	Output is correct
8	Correct	0 ms	3260 KB	Output is correct
9	Correct	0 ms	3260 KB	Output is correct
10	Correct	0 ms	3260 KB	Output is correct
11	Correct	0 ms	3392 KB	Output is correct
12	Correct	3 ms	6376 KB	Output is correct
13	Correct	6 ms	6388 KB	Output is correct
14	Correct	0 ms	3260 KB	Output is correct
15	Correct	0 ms	3260 KB	Output is correct
16	Correct	0 ms	3260 KB	Output is correct
17	Correct	0 ms	3528 KB	Output is correct
18	Correct	0 ms	3260 KB	Output is correct
19	Correct	0 ms	3260 KB	Output is correct
20	Correct	53 ms	35308 KB	Output is correct
21	Correct	0 ms	3260 KB	Output is correct
22	Correct	0 ms	3260 KB	Output is correct
23	Correct	0 ms	3260 KB	Output is correct
24	Correct	3 ms	3392 KB	Output is correct
25	Correct	0 ms	3392 KB	Output is correct
26	Correct	59 ms	52580 KB	Output is correct
27	Correct	46 ms	52516 KB	Output is correct
28	Correct	0 ms	3524 KB	Output is correct
29	Correct	3 ms	4144 KB	Output is correct
30	Correct	0 ms	3528 KB	Output is correct
31	Correct	0 ms	3660 KB	Output is correct
32	Correct	0 ms	3660 KB	Output is correct
33	Correct	3 ms	4736 KB	Output is correct
34	Correct	3 ms	4924 KB	Output is correct
35	Correct	9 ms	4868 KB	Output is correct
36	Correct	0 ms	3536 KB	Output is correct
37	Correct	19 ms	6668 KB	Output is correct
38	Correct	16 ms	5992 KB	Output is correct
39	Correct	13 ms	6216 KB	Output is correct
40	Correct	13 ms	6100 KB	Output is correct
41	Correct	16 ms	5812 KB	Output is correct
42	Memory limit exceeded	213 ms	262144 KB	Memory limit exceeded
43	Halted	0 ms	0 KB	-

답안 #39454

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