oj.uz

답안 #318119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
318119 2020-10-31T13:17:29 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 685 ms 157540 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 = 2e7;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 78820 KB Output is correct
2 Correct 267 ms 156900 KB Output is correct
3 Correct 219 ms 79844 KB Output is correct
4 Correct 221 ms 156900 KB Output is correct
5 Correct 243 ms 156900 KB Output is correct
6 Correct 199 ms 78820 KB Output is correct
7 Correct 217 ms 79844 KB Output is correct
8 Correct 226 ms 82276 KB Output is correct
9 Correct 287 ms 156884 KB Output is correct
10 Correct 324 ms 156900 KB Output is correct
11 Correct 307 ms 156900 KB Output is correct
12 Correct 217 ms 156916 KB Output is correct
13 Correct 513 ms 156900 KB Output is correct
14 Correct 518 ms 156900 KB Output is correct
15 Correct 287 ms 156888 KB Output is correct
16 Correct 271 ms 156900 KB Output is correct
17 Correct 269 ms 156900 KB Output is correct
18 Correct 220 ms 156900 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 156900 KB Output is correct
2 Correct 284 ms 156900 KB Output is correct
3 Correct 624 ms 156984 KB Output is correct
4 Correct 297 ms 156900 KB Output is correct
5 Correct 451 ms 157008 KB Output is correct
6 Correct 264 ms 156900 KB Output is correct
7 Correct 260 ms 157032 KB Output is correct
8 Correct 293 ms 156900 KB Output is correct
9 Correct 526 ms 156904 KB Output is correct
10 Correct 628 ms 156900 KB Output is correct
11 Correct 614 ms 156900 KB Output is correct
12 Correct 370 ms 156900 KB Output is correct
13 Correct 237 ms 156900 KB Output is correct
14 Correct 296 ms 156900 KB Output is correct
15 Correct 514 ms 156900 KB Output is correct
16 Correct 277 ms 156900 KB Output is correct
17 Correct 531 ms 156900 KB Output is correct
18 Correct 517 ms 157028 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 525 ms 157028 KB Output is correct
2 Correct 641 ms 157028 KB Output is correct
3 Correct 645 ms 157028 KB Output is correct
4 Correct 405 ms 157156 KB Output is correct
5 Correct 318 ms 157156 KB Output is correct
6 Correct 525 ms 157156 KB Output is correct
7 Correct 477 ms 157028 KB Output is correct
8 Correct 521 ms 157028 KB Output is correct
9 Correct 518 ms 157028 KB Output is correct
10 Correct 430 ms 156900 KB Output is correct
11 Correct 374 ms 156900 KB Output is correct
12 Correct 484 ms 157032 KB Output is correct
13 Correct 610 ms 157156 KB Output is correct
14 Correct 367 ms 157540 KB Output is correct
15 Correct 508 ms 157028 KB Output is correct
16 Correct 565 ms 157156 KB Output is correct
17 Correct 508 ms 156884 KB Output is correct
18 Correct 636 ms 156924 KB Output is correct
19 Correct 253 ms 157028 KB Output is correct
20 Correct 641 ms 157028 KB Output is correct
21 Correct 419 ms 157540 KB Output is correct
22 Correct 641 ms 157148 KB Output is correct
23 Correct 324 ms 157260 KB Output is correct
24 Correct 273 ms 157152 KB Output is correct
25 Correct 457 ms 157284 KB Output is correct
26 Correct 397 ms 157144 KB Output is correct
27 Correct 685 ms 157136 KB Output is correct
28 Correct 272 ms 157156 KB Output is correct
29 Correct 613 ms 157156 KB Output is correct
30 Correct 578 ms 157156 KB Output is correct
31 Correct 311 ms 157156 KB Output is correct
32 Correct 342 ms 157468 KB Output is correct
33 Correct 244 ms 157156 KB Output is correct
34 Correct 472 ms 157156 KB Output is correct
35 Correct 285 ms 157284 KB Output is correct
36 Correct 626 ms 157156 KB Output is correct
37 Correct 317 ms 157160 KB Output is correct
38 Correct 521 ms 157156 KB Output is correct
39 Correct 288 ms 157156 KB Output is correct
40 Correct 458 ms 157136 KB Output is correct
41 Correct 420 ms 157028 KB Output is correct
42 Correct 571 ms 157284 KB Output is correct