oj.uz

Submission #318116

# Submission time Handle Problem Language Result Execution time Memory
318116 2020-10-31T13:16:39 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 13 ms 2028 KB 
#include "bits/stdc++.h"
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 1e5;
int jmp[MXN+2], ans[MXN+2];

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int m, q; cin >> m >> q;
	for_(i, 0, m) {
		int k; cin >> k;
		for (int j = k; j <= MXN; j += k) {
			jmp[j-1] = max(jmp[j-1], k-1);
		}
	}
	
	for (int i = MXN; i >= 1; i--) jmp[i] = max(jmp[i], jmp[i+1]-1);
	
	for_(i, 1, MXN+1) if (jmp[i] and (ans[i-jmp[i]] or i == jmp[i])) ans[i] = ans[i-jmp[i]]+1;
	
	for_(i, 0, q) {
		int k; cin >> k;
		if (ans[k]) cout << ans[k];
		else cout << "oo";
		cout << endl;
	}

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 2 ms 1260 KB Output is correct
4 Correct 3 ms 1132 KB Output is correct
5 Correct 1 ms 1132 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 2 ms 1132 KB Output is correct
8 Correct 2 ms 1132 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 2 ms 1132 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 1 ms 1132 KB Output is correct
13 Correct 2 ms 1132 KB Output is correct
14 Correct 3 ms 1132 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct
16 Correct 2 ms 1132 KB Output is correct
17 Correct 3 ms 1132 KB Output is correct
18 Correct 3 ms 1132 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 12 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 10 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 8 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 10 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 10 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 7 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 3 ms 2024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 7 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 12 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 12 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 8 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 8 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 13 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 13 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 8 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 10 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 6 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 7 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 8 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 8 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 13 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 6 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 12 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 12 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 9 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 12 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 12 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 12 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 4 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 12 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 3 ms 2028 KB Execution killed with signal 11 (could be triggered by violating memory limits)