답안 #46582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
46582 2018-04-21T14:46:03 Z aome Jakarta Skyscrapers (APIO15_skyscraper) C++17
100 / 100
852 ms 38268 KB
#include <bits/stdc++.h>

using namespace std;

const int N = 30005;
const int B = 205;
const int INF = 0x3f3f3f3f;

int n, m;
int b[N], p[N];
int f[N][B];
vector<int> vec[N];

struct State {
	int w, x, y;

	State (int w, int x, int y) : w(w), x(x), y(y) {}

	bool operator < (const State& rhs) const {
		return w > rhs.w;
	}
};

int solve() {
	memset(f, INF, sizeof f);
	priority_queue<State> pq;
	pq.push(State(0, b[0], 0));
	f[b[0]][0] = 0;
	while (pq.size()) {
		State u = pq.top(); pq.pop();
		if (u.w != f[u.x][u.y]) continue;
		if (u.x == b[1]) return u.w;
		if (u.y) {
			if (f[u.x][0] > u.w) {
				f[u.x][0] = u.w, pq.push(State(u.w, u.x, 0));
			}
			if (u.x + u.y < n && f[u.x + u.y][u.y] > u.w + 1) {
				f[u.x + u.y][u.y] = u.w + 1, pq.push(State(u.w + 1, u.x + u.y, u.y));
			}
			if (u.x - u.y >= 0 && f[u.x - u.y][u.y] > u.w + 1) {
				f[u.x - u.y][u.y] = u.w + 1, pq.push(State(u.w + 1, u.x - u.y, u.y));
			}
		}
		else {
			for (auto i : vec[u.x]) {
				if (p[i] >= B) {
					for (int j = u.x % p[i]; j < n; j += p[i]) {
						if (f[j][0] > u.w + abs(u.x - j) / p[i]) {
							f[j][0] = u.w + abs(u.x - j) / p[i], pq.push(State(f[j][0], j, 0));
						}
					}
				}
				else {
					if (f[u.x][p[i]] > u.w) {
						f[u.x][p[i]] = u.w, pq.push(State(u.w, u.x, p[i]));
					}
				}
			}
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		cin >> b[i] >> p[i], vec[b[i]].push_back(i);
	}
	cout << solve();
}
# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 25080 KB Output is correct
2 Correct 20 ms 25200 KB Output is correct
3 Correct 19 ms 25268 KB Output is correct
4 Correct 21 ms 25380 KB Output is correct
5 Correct 21 ms 25436 KB Output is correct
6 Correct 19 ms 25480 KB Output is correct
7 Correct 20 ms 25480 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 25480 KB Output is correct
2 Correct 20 ms 25580 KB Output is correct
3 Correct 21 ms 25580 KB Output is correct
4 Correct 21 ms 25580 KB Output is correct
5 Correct 24 ms 25580 KB Output is correct
6 Correct 20 ms 25580 KB Output is correct
7 Correct 24 ms 25580 KB Output is correct
8 Correct 19 ms 25580 KB Output is correct
9 Correct 20 ms 25580 KB Output is correct
10 Correct 20 ms 25580 KB Output is correct
11 Correct 21 ms 25632 KB Output is correct
12 Correct 20 ms 25644 KB Output is correct
13 Correct 21 ms 25644 KB Output is correct
14 Correct 23 ms 25888 KB Output is correct
15 Correct 22 ms 25888 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 25888 KB Output is correct
2 Correct 21 ms 25888 KB Output is correct
3 Correct 20 ms 25888 KB Output is correct
4 Correct 22 ms 25888 KB Output is correct
5 Correct 22 ms 25888 KB Output is correct
6 Correct 21 ms 25888 KB Output is correct
7 Correct 19 ms 25888 KB Output is correct
8 Correct 20 ms 25888 KB Output is correct
9 Correct 20 ms 25888 KB Output is correct
10 Correct 20 ms 25888 KB Output is correct
11 Correct 22 ms 25888 KB Output is correct
12 Correct 22 ms 25888 KB Output is correct
13 Correct 21 ms 25888 KB Output is correct
14 Correct 22 ms 25932 KB Output is correct
15 Correct 22 ms 25932 KB Output is correct
16 Correct 21 ms 25932 KB Output is correct
17 Correct 22 ms 25932 KB Output is correct
18 Correct 20 ms 25932 KB Output is correct
19 Correct 25 ms 25932 KB Output is correct
20 Correct 23 ms 25932 KB Output is correct
21 Correct 20 ms 25932 KB Output is correct
22 Correct 21 ms 25932 KB Output is correct
23 Correct 25 ms 25940 KB Output is correct
24 Correct 23 ms 25940 KB Output is correct
25 Correct 22 ms 26060 KB Output is correct
26 Correct 22 ms 26060 KB Output is correct
27 Correct 22 ms 26060 KB Output is correct
28 Correct 24 ms 26060 KB Output is correct
29 Correct 26 ms 26060 KB Output is correct
30 Correct 27 ms 26060 KB Output is correct
31 Correct 24 ms 26060 KB Output is correct
32 Correct 25 ms 26060 KB Output is correct
33 Correct 31 ms 26064 KB Output is correct
34 Correct 28 ms 26076 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 26076 KB Output is correct
2 Correct 21 ms 26076 KB Output is correct
3 Correct 22 ms 26076 KB Output is correct
4 Correct 21 ms 26076 KB Output is correct
5 Correct 22 ms 26076 KB Output is correct
6 Correct 21 ms 26108 KB Output is correct
7 Correct 21 ms 26108 KB Output is correct
8 Correct 21 ms 26108 KB Output is correct
9 Correct 21 ms 26108 KB Output is correct
10 Correct 21 ms 26108 KB Output is correct
11 Correct 22 ms 26132 KB Output is correct
12 Correct 21 ms 26148 KB Output is correct
13 Correct 21 ms 26156 KB Output is correct
14 Correct 23 ms 26168 KB Output is correct
15 Correct 21 ms 26180 KB Output is correct
16 Correct 21 ms 26192 KB Output is correct
17 Correct 22 ms 26200 KB Output is correct
18 Correct 21 ms 26216 KB Output is correct
19 Correct 21 ms 26216 KB Output is correct
20 Correct 22 ms 26236 KB Output is correct
21 Correct 21 ms 26236 KB Output is correct
22 Correct 21 ms 26272 KB Output is correct
23 Correct 24 ms 26280 KB Output is correct
24 Correct 27 ms 26296 KB Output is correct
25 Correct 21 ms 26304 KB Output is correct
26 Correct 21 ms 26356 KB Output is correct
27 Correct 23 ms 26356 KB Output is correct
28 Correct 24 ms 26388 KB Output is correct
29 Correct 26 ms 26408 KB Output is correct
30 Correct 23 ms 26408 KB Output is correct
31 Correct 25 ms 26532 KB Output is correct
32 Correct 24 ms 26532 KB Output is correct
33 Correct 34 ms 26532 KB Output is correct
34 Correct 33 ms 26532 KB Output is correct
35 Correct 36 ms 27096 KB Output is correct
36 Correct 23 ms 27096 KB Output is correct
37 Correct 29 ms 27228 KB Output is correct
38 Correct 35 ms 27644 KB Output is correct
39 Correct 28 ms 27780 KB Output is correct
40 Correct 28 ms 28044 KB Output is correct
41 Correct 31 ms 28380 KB Output is correct
42 Correct 30 ms 28572 KB Output is correct
43 Correct 28 ms 28684 KB Output is correct
44 Correct 27 ms 28880 KB Output is correct
45 Correct 79 ms 29664 KB Output is correct
46 Correct 48 ms 29856 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 29856 KB Output is correct
2 Correct 25 ms 29856 KB Output is correct
3 Correct 21 ms 29856 KB Output is correct
4 Correct 25 ms 29856 KB Output is correct
5 Correct 21 ms 29856 KB Output is correct
6 Correct 21 ms 29856 KB Output is correct
7 Correct 22 ms 29856 KB Output is correct
8 Correct 21 ms 29856 KB Output is correct
9 Correct 24 ms 29856 KB Output is correct
10 Correct 21 ms 29856 KB Output is correct
11 Correct 22 ms 29856 KB Output is correct
12 Correct 21 ms 29856 KB Output is correct
13 Correct 22 ms 29856 KB Output is correct
14 Correct 22 ms 29856 KB Output is correct
15 Correct 22 ms 29856 KB Output is correct
16 Correct 24 ms 29856 KB Output is correct
17 Correct 23 ms 29856 KB Output is correct
18 Correct 22 ms 29856 KB Output is correct
19 Correct 22 ms 29856 KB Output is correct
20 Correct 22 ms 29856 KB Output is correct
21 Correct 20 ms 29856 KB Output is correct
22 Correct 20 ms 29856 KB Output is correct
23 Correct 21 ms 29856 KB Output is correct
24 Correct 22 ms 29856 KB Output is correct
25 Correct 22 ms 29856 KB Output is correct
26 Correct 22 ms 29856 KB Output is correct
27 Correct 22 ms 29856 KB Output is correct
28 Correct 22 ms 29856 KB Output is correct
29 Correct 26 ms 29856 KB Output is correct
30 Correct 27 ms 29856 KB Output is correct
31 Correct 25 ms 29856 KB Output is correct
32 Correct 23 ms 29856 KB Output is correct
33 Correct 36 ms 29856 KB Output is correct
34 Correct 28 ms 29856 KB Output is correct
35 Correct 30 ms 29988 KB Output is correct
36 Correct 27 ms 29988 KB Output is correct
37 Correct 34 ms 30120 KB Output is correct
38 Correct 30 ms 30500 KB Output is correct
39 Correct 33 ms 30796 KB Output is correct
40 Correct 28 ms 30940 KB Output is correct
41 Correct 35 ms 31324 KB Output is correct
42 Correct 28 ms 31496 KB Output is correct
43 Correct 27 ms 31720 KB Output is correct
44 Correct 28 ms 31800 KB Output is correct
45 Correct 70 ms 32588 KB Output is correct
46 Correct 47 ms 32796 KB Output is correct
47 Correct 31 ms 33160 KB Output is correct
48 Correct 28 ms 33160 KB Output is correct
49 Correct 28 ms 33160 KB Output is correct
50 Correct 26 ms 33160 KB Output is correct
51 Correct 45 ms 34396 KB Output is correct
52 Correct 43 ms 34728 KB Output is correct
53 Correct 33 ms 34728 KB Output is correct
54 Correct 23 ms 34728 KB Output is correct
55 Correct 23 ms 34728 KB Output is correct
56 Correct 34 ms 35316 KB Output is correct
57 Correct 22 ms 35316 KB Output is correct
58 Correct 30 ms 35316 KB Output is correct
59 Correct 32 ms 35316 KB Output is correct
60 Correct 32 ms 35316 KB Output is correct
61 Correct 32 ms 35316 KB Output is correct
62 Correct 65 ms 36316 KB Output is correct
63 Correct 72 ms 37532 KB Output is correct
64 Correct 86 ms 37760 KB Output is correct
65 Correct 353 ms 38032 KB Output is correct
66 Correct 852 ms 38124 KB Output is correct
67 Correct 437 ms 38268 KB Output is correct