oj.uz

Submission #307086

# Submission time Handle Problem Language Result Execution time Memory
307086 2020-09-27T02:00:29 Z Rainbowbunny Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 823 ms 236924 KB 
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using cd = complex <double>;
 
const long long INF = 1e15;
const int mod = 998244353;//1e9 + 7;//786433;
const double Pi = acos(-1);
 
void Fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
 
int m, q, p;
int Seive[20000005], dp[10000005];
 
signed main()
{
	Fastio();
	cin >> m >> q;
	for(int i = 1; i <= m; i++)
	{
		cin >> p;
		for(int j = p - 1; j <= 20000000; j = j + p)
		{
			Seive[j] = max(Seive[j], p - 1);
		}
	}
	for(int i = 20000000; i > 1; i--)
	{
		Seive[i - 1] = max(Seive[i - 1], Seive[i] - 1);
	}
	for(int i = 1; i <= 10000000; i++)
	{
		dp[i] = 999999999;
		dp[i] = dp[i - Seive[i]] + 1;
	}
	while(q--)
	{
		int n;
		cin >> n;
		if(dp[n] >= 10000005)
		{
			cout << "oo\n";
			continue;
		}
		cout << dp[n] << '\n';
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 235128 KB Output is correct
2 Correct 302 ms 235128 KB Output is correct
3 Correct 264 ms 235256 KB Output is correct
4 Correct 231 ms 235256 KB Output is correct
5 Correct 260 ms 235128 KB Output is correct
6 Correct 235 ms 235128 KB Output is correct
7 Correct 267 ms 235128 KB Output is correct
8 Correct 289 ms 235256 KB Output is correct
9 Correct 335 ms 235128 KB Output is correct
10 Correct 388 ms 235132 KB Output is correct
11 Correct 363 ms 235256 KB Output is correct
12 Correct 225 ms 235128 KB Output is correct
13 Correct 619 ms 235256 KB Output is correct
14 Correct 613 ms 235384 KB Output is correct
15 Correct 316 ms 235128 KB Output is correct
16 Correct 293 ms 235128 KB Output is correct
17 Correct 280 ms 235288 KB Output is correct
18 Correct 224 ms 235384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 235256 KB Output is correct
2 Correct 307 ms 235868 KB Output is correct
3 Correct 760 ms 235640 KB Output is correct
4 Correct 322 ms 235128 KB Output is correct
5 Correct 513 ms 235640 KB Output is correct
6 Correct 279 ms 235128 KB Output is correct
7 Correct 260 ms 235256 KB Output is correct
8 Correct 316 ms 235256 KB Output is correct
9 Correct 585 ms 235768 KB Output is correct
10 Correct 736 ms 235768 KB Output is correct
11 Correct 716 ms 235640 KB Output is correct
12 Correct 412 ms 235256 KB Output is correct
13 Correct 245 ms 235256 KB Output is correct
14 Correct 312 ms 235256 KB Output is correct
15 Correct 601 ms 235384 KB Output is correct
16 Correct 288 ms 235896 KB Output is correct
17 Correct 630 ms 235128 KB Output is correct
18 Correct 608 ms 236024 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 236024 KB Output is correct
2 Correct 752 ms 235896 KB Output is correct
3 Correct 764 ms 236152 KB Output is correct
4 Correct 461 ms 236152 KB Output is correct
5 Correct 341 ms 236920 KB Output is correct
6 Correct 609 ms 236280 KB Output is correct
7 Correct 524 ms 236412 KB Output is correct
8 Correct 622 ms 236020 KB Output is correct
9 Correct 618 ms 236152 KB Output is correct
10 Correct 483 ms 235516 KB Output is correct
11 Correct 415 ms 235512 KB Output is correct
12 Correct 574 ms 235424 KB Output is correct
13 Correct 716 ms 236472 KB Output is correct
14 Correct 434 ms 236536 KB Output is correct
15 Correct 618 ms 235512 KB Output is correct
16 Correct 676 ms 235512 KB Output is correct
17 Correct 578 ms 235768 KB Output is correct
18 Correct 760 ms 235896 KB Output is correct
19 Correct 260 ms 235384 KB Output is correct
20 Correct 761 ms 236132 KB Output is correct
21 Correct 495 ms 236664 KB Output is correct
22 Correct 762 ms 236920 KB Output is correct
23 Correct 341 ms 236536 KB Output is correct
24 Correct 280 ms 236280 KB Output is correct
25 Correct 499 ms 236280 KB Output is correct
26 Correct 469 ms 236152 KB Output is correct
27 Correct 823 ms 236448 KB Output is correct
28 Correct 289 ms 236280 KB Output is correct
29 Correct 695 ms 236920 KB Output is correct
30 Correct 624 ms 236664 KB Output is correct
31 Correct 322 ms 236152 KB Output is correct
32 Correct 366 ms 236152 KB Output is correct
33 Correct 252 ms 236152 KB Output is correct
34 Correct 529 ms 236664 KB Output is correct
35 Correct 314 ms 236280 KB Output is correct
36 Correct 782 ms 236924 KB Output is correct
37 Correct 364 ms 236920 KB Output is correct
38 Correct 630 ms 236188 KB Output is correct
39 Correct 314 ms 236280 KB Output is correct
40 Correct 555 ms 236152 KB Output is correct
41 Correct 471 ms 236536 KB Output is correct
42 Correct 710 ms 236428 KB Output is correct