oj.uz

Submission #631369

# Submission time Handle Problem Language Result Execution time Memory
631369 2022-08-18T03:53:38 Z uylulu Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 441 ms 79120 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define endl "\n"

const int N = 1e7,len = 1e5;

int mx[N + 1],dp[N + 1],num[len + 1];
int m,q,lim;

int lcm(int a,int b) {
	return a*b/(__gcd(a,b));
}

void init() {
	lim = num[1];
	for(int i = 2;i <= m;i++) {
		if(lim > N) break;
		lim = lcm(lim,num[i]);
	}
	for(int i = 1;i <= m;i++) {
		for(int j = 1;num[i]*j <= N;j++) {
			mx[num[i]*j] = max(num[i],mx[num[i]*j]);
		}
	}
	dp[0] = 0;
	for(int i = 1;i < num[m];i++) {
		dp[i] = 1;
	}
	int lst = 0,temp = 0;
	for(int i = 1;i < num[m];i++) {
		if(temp < (mx[i] - 1) - (num[m] - i)) {
			temp = (mx[i] - 1) - (num[m] - i);
			lst = i;
		}
	}
	for(int i = num[m];i <= min(lim - 1,N);i++) {
		while(mx[lst] - 1 < (i - lst)) lst++;
		dp[i] = dp[lst] + 1;
	}
}

signed main() {
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);

	cin>>m>>q;
	for(int i = 1;i <= m;i++) cin>>num[i];
	init();
	while(q--) {
		int x;
		cin>>x;
		if(x >= lim) {
			cout<<"oo"<<endl;
		} else {
			cout<<dp[x]<<endl;
		}
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 39436 KB Output is correct
2 Correct 84 ms 78448 KB Output is correct
3 Correct 48 ms 40412 KB Output is correct
4 Correct 70 ms 78532 KB Output is correct
5 Correct 72 ms 78540 KB Output is correct
6 Correct 30 ms 39396 KB Output is correct
7 Correct 40 ms 40404 KB Output is correct
8 Correct 45 ms 42964 KB Output is correct
9 Correct 91 ms 78456 KB Output is correct
10 Correct 109 ms 78596 KB Output is correct
11 Correct 103 ms 78460 KB Output is correct
12 Correct 56 ms 78668 KB Output is correct
13 Correct 166 ms 78464 KB Output is correct
14 Correct 175 ms 78468 KB Output is correct
15 Correct 96 ms 78468 KB Output is correct
16 Correct 88 ms 78468 KB Output is correct
17 Correct 89 ms 78588 KB Output is correct
18 Correct 71 ms 78556 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 78528 KB Output is correct
2 Correct 100 ms 78852 KB Output is correct
3 Correct 216 ms 78748 KB Output is correct
4 Correct 94 ms 78476 KB Output is correct
5 Correct 158 ms 78668 KB Output is correct
6 Correct 71 ms 78452 KB Output is correct
7 Correct 84 ms 78508 KB Output is correct
8 Correct 82 ms 78448 KB Output is correct
9 Correct 182 ms 78824 KB Output is correct
10 Correct 236 ms 78824 KB Output is correct
11 Correct 242 ms 78616 KB Output is correct
12 Correct 125 ms 78540 KB Output is correct
13 Correct 62 ms 78548 KB Output is correct
14 Correct 83 ms 78560 KB Output is correct
15 Correct 199 ms 78656 KB Output is correct
16 Correct 97 ms 78832 KB Output is correct
17 Correct 175 ms 78476 KB Output is correct
18 Correct 205 ms 78952 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 78752 KB Output is correct
2 Correct 267 ms 78800 KB Output is correct
3 Correct 331 ms 78796 KB Output is correct
4 Correct 285 ms 78740 KB Output is correct
5 Correct 275 ms 79100 KB Output is correct
6 Correct 330 ms 78752 KB Output is correct
7 Correct 260 ms 79056 KB Output is correct
8 Correct 275 ms 78792 KB Output is correct
9 Correct 244 ms 78844 KB Output is correct
10 Correct 156 ms 78604 KB Output is correct
11 Correct 151 ms 78608 KB Output is correct
12 Correct 188 ms 78628 KB Output is correct
13 Correct 331 ms 78952 KB Output is correct
14 Correct 266 ms 79064 KB Output is correct
15 Correct 231 ms 78592 KB Output is correct
16 Correct 220 ms 78624 KB Output is correct
17 Correct 202 ms 78752 KB Output is correct
18 Correct 256 ms 78796 KB Output is correct
19 Correct 114 ms 78540 KB Output is correct
20 Correct 311 ms 78984 KB Output is correct
21 Correct 297 ms 79072 KB Output is correct
22 Correct 441 ms 79120 KB Output is correct
23 Correct 276 ms 78888 KB Output is correct
24 Correct 231 ms 78728 KB Output is correct
25 Correct 278 ms 78900 KB Output is correct
26 Correct 278 ms 78792 KB Output is correct
27 Correct 348 ms 79112 KB Output is correct
28 Correct 241 ms 78840 KB Output is correct
29 Correct 395 ms 79024 KB Output is correct
30 Correct 361 ms 79036 KB Output is correct
31 Correct 217 ms 78792 KB Output is correct
32 Correct 255 ms 78760 KB Output is correct
33 Correct 220 ms 78700 KB Output is correct
34 Correct 250 ms 78988 KB Output is correct
35 Correct 238 ms 78784 KB Output is correct
36 Correct 378 ms 79068 KB Output is correct
37 Correct 259 ms 79100 KB Output is correct
38 Correct 323 ms 78864 KB Output is correct
39 Correct 229 ms 78852 KB Output is correct
40 Correct 278 ms 78852 KB Output is correct
41 Correct 241 ms 78988 KB Output is correct
42 Correct 368 ms 78856 KB Output is correct