oj.uz

Submission #552612

# Submission time Handle Problem Language Result Execution time Memory
552612 2022-04-23T12:21:23 Z QwertyPi Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 1000 ms 67400 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

int dp[30001];
vector<int> G[30001];
int A[30001][2];
int main(){
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < k; i++){
		cin >> A[i][0] >> A[i][1];
		G[A[i][0]].push_back(A[i][1]);
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	q.push({0, A[0][0]});
	fill(dp, dp + n, (1 << 30));
	while(q.size()){
		pair<int, int> qe = q.top(); q.pop();
		int v = qe.se, w = qe.fi;
		if(dp[v] != (1 << 30)) continue;
		dp[v] = w;
		// cout << v << ' ' << w << endl;
		for(auto i : G[v]){
			for(int j = v % i; j < n; j += i){
				int d = abs(v - j) / i;
				if(dp[j] > w + d) q.push({w + d, j});
			}
		}
	}
	cout << (dp[A[1][0]] == (1 << 30) ? -1 : dp[A[1][0]]) << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1008 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 1012 KB Output is correct
8 Correct 1 ms 984 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 3 ms 1024 KB Output is correct
12 Correct 6 ms 1616 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 2 ms 1108 KB Output is correct
15 Correct 2 ms 1020 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 2 ms 1028 KB Output is correct
12 Correct 7 ms 1664 KB Output is correct
13 Correct 3 ms 1108 KB Output is correct
14 Correct 2 ms 1108 KB Output is correct
15 Correct 2 ms 1108 KB Output is correct
16 Correct 1 ms 980 KB Output is correct
17 Correct 3 ms 1156 KB Output is correct
18 Correct 2 ms 980 KB Output is correct
19 Correct 1 ms 980 KB Output is correct
20 Correct 402 ms 9484 KB Output is correct
21 Correct 1 ms 980 KB Output is correct
22 Correct 1 ms 980 KB Output is correct
23 Correct 1 ms 980 KB Output is correct
24 Correct 2 ms 1108 KB Output is correct
25 Correct 2 ms 1156 KB Output is correct
26 Correct 43 ms 3260 KB Output is correct
27 Correct 72 ms 5216 KB Output is correct
28 Correct 2 ms 1108 KB Output is correct
29 Correct 10 ms 1616 KB Output is correct
30 Correct 3 ms 1236 KB Output is correct
31 Correct 4 ms 1364 KB Output is correct
32 Correct 3 ms 1236 KB Output is correct
33 Correct 19 ms 2124 KB Output is correct
34 Correct 20 ms 2124 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1016 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 1016 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 1016 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 2 ms 1108 KB Output is correct
12 Correct 7 ms 1616 KB Output is correct
13 Correct 4 ms 980 KB Output is correct
14 Correct 2 ms 1020 KB Output is correct
15 Correct 2 ms 1020 KB Output is correct
16 Correct 1 ms 980 KB Output is correct
17 Correct 4 ms 1156 KB Output is correct
18 Correct 2 ms 980 KB Output is correct
19 Correct 1 ms 980 KB Output is correct
20 Correct 357 ms 9432 KB Output is correct
21 Correct 2 ms 980 KB Output is correct
22 Correct 2 ms 1020 KB Output is correct
23 Correct 2 ms 980 KB Output is correct
24 Correct 3 ms 1108 KB Output is correct
25 Correct 2 ms 1108 KB Output is correct
26 Correct 44 ms 3144 KB Output is correct
27 Correct 72 ms 5236 KB Output is correct
28 Correct 2 ms 1108 KB Output is correct
29 Correct 9 ms 1660 KB Output is correct
30 Correct 3 ms 1236 KB Output is correct
31 Correct 5 ms 1364 KB Output is correct
32 Correct 3 ms 1236 KB Output is correct
33 Correct 20 ms 2128 KB Output is correct
34 Correct 20 ms 2124 KB Output is correct
35 Correct 28 ms 2224 KB Output is correct
36 Correct 4 ms 1236 KB Output is correct
37 Correct 34 ms 3668 KB Output is correct
38 Correct 40 ms 2864 KB Output is correct
39 Correct 42 ms 2832 KB Output is correct
40 Correct 34 ms 2824 KB Output is correct
41 Correct 33 ms 2900 KB Output is correct
42 Correct 863 ms 34440 KB Output is correct
43 Execution timed out 1085 ms 67304 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1024 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 1008 KB Output is correct
7 Correct 1 ms 1016 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 2 ms 1020 KB Output is correct
11 Correct 2 ms 1108 KB Output is correct
12 Correct 7 ms 1616 KB Output is correct
13 Correct 4 ms 1108 KB Output is correct
14 Correct 2 ms 1108 KB Output is correct
15 Correct 2 ms 1108 KB Output is correct
16 Correct 1 ms 980 KB Output is correct
17 Correct 3 ms 1236 KB Output is correct
18 Correct 2 ms 980 KB Output is correct
19 Correct 1 ms 980 KB Output is correct
20 Correct 347 ms 9336 KB Output is correct
21 Correct 1 ms 1024 KB Output is correct
22 Correct 1 ms 980 KB Output is correct
23 Correct 2 ms 980 KB Output is correct
24 Correct 3 ms 1108 KB Output is correct
25 Correct 3 ms 1072 KB Output is correct
26 Correct 54 ms 3216 KB Output is correct
27 Correct 79 ms 5176 KB Output is correct
28 Correct 2 ms 1108 KB Output is correct
29 Correct 9 ms 1616 KB Output is correct
30 Correct 3 ms 1236 KB Output is correct
31 Correct 4 ms 1396 KB Output is correct
32 Correct 3 ms 1236 KB Output is correct
33 Correct 22 ms 2168 KB Output is correct
34 Correct 19 ms 2168 KB Output is correct
35 Correct 26 ms 2260 KB Output is correct
36 Correct 6 ms 1236 KB Output is correct
37 Correct 41 ms 3652 KB Output is correct
38 Correct 31 ms 2812 KB Output is correct
39 Correct 34 ms 2864 KB Output is correct
40 Correct 40 ms 2896 KB Output is correct
41 Correct 34 ms 2812 KB Output is correct
42 Correct 864 ms 34496 KB Output is correct
43 Execution timed out 1088 ms 67400 KB Time limit exceeded
44 Halted 0 ms 0 KB -