oj.uz

Submission #631371

# Submission time Handle Problem Language Result Execution time Memory
631371 2022-08-18T04:01:10 Z uylulu Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 439 ms 79220 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 36 ms 39468 KB Output is correct
2 Correct 80 ms 78460 KB Output is correct
3 Correct 38 ms 40448 KB Output is correct
4 Correct 68 ms 78512 KB Output is correct
5 Correct 82 ms 78464 KB Output is correct
6 Correct 31 ms 39436 KB Output is correct
7 Correct 41 ms 40392 KB Output is correct
8 Correct 49 ms 42896 KB Output is correct
9 Correct 92 ms 78440 KB Output is correct
10 Correct 115 ms 78460 KB Output is correct
11 Correct 96 ms 78500 KB Output is correct
12 Correct 54 ms 78472 KB Output is correct
13 Correct 173 ms 78464 KB Output is correct
14 Correct 189 ms 78508 KB Output is correct
15 Correct 88 ms 78476 KB Output is correct
16 Correct 87 ms 78460 KB Output is correct
17 Correct 99 ms 78492 KB Output is correct
18 Correct 74 ms 78464 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 78588 KB Output is correct
2 Correct 91 ms 78896 KB Output is correct
3 Correct 229 ms 78740 KB Output is correct
4 Correct 97 ms 78476 KB Output is correct
5 Correct 146 ms 78756 KB Output is correct
6 Correct 69 ms 78540 KB Output is correct
7 Correct 85 ms 78632 KB Output is correct
8 Correct 87 ms 78496 KB Output is correct
9 Correct 177 ms 78748 KB Output is correct
10 Correct 242 ms 78756 KB Output is correct
11 Correct 227 ms 78616 KB Output is correct
12 Correct 117 ms 78540 KB Output is correct
13 Correct 66 ms 78524 KB Output is correct
14 Correct 95 ms 78472 KB Output is correct
15 Correct 207 ms 78664 KB Output is correct
16 Correct 103 ms 78936 KB Output is correct
17 Correct 174 ms 78532 KB Output is correct
18 Correct 187 ms 78860 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 78772 KB Output is correct
2 Correct 263 ms 78788 KB Output is correct
3 Correct 347 ms 78824 KB Output is correct
4 Correct 263 ms 78896 KB Output is correct
5 Correct 271 ms 79096 KB Output is correct
6 Correct 332 ms 78836 KB Output is correct
7 Correct 254 ms 78988 KB Output is correct
8 Correct 237 ms 78788 KB Output is correct
9 Correct 247 ms 78956 KB Output is correct
10 Correct 183 ms 78588 KB Output is correct
11 Correct 148 ms 78604 KB Output is correct
12 Correct 193 ms 78612 KB Output is correct
13 Correct 340 ms 78968 KB Output is correct
14 Correct 281 ms 79220 KB Output is correct
15 Correct 203 ms 78740 KB Output is correct
16 Correct 225 ms 78600 KB Output is correct
17 Correct 216 ms 78668 KB Output is correct
18 Correct 291 ms 78796 KB Output is correct
19 Correct 99 ms 78612 KB Output is correct
20 Correct 313 ms 78904 KB Output is correct
21 Correct 308 ms 79104 KB Output is correct
22 Correct 439 ms 79108 KB Output is correct
23 Correct 266 ms 78924 KB Output is correct
24 Correct 219 ms 78740 KB Output is correct
25 Correct 317 ms 78988 KB Output is correct
26 Correct 255 ms 78744 KB Output is correct
27 Correct 345 ms 78988 KB Output is correct
28 Correct 259 ms 78800 KB Output is correct
29 Correct 389 ms 79064 KB Output is correct
30 Correct 377 ms 79080 KB Output is correct
31 Correct 236 ms 78832 KB Output is correct
32 Correct 250 ms 78768 KB Output is correct
33 Correct 242 ms 78796 KB Output is correct
34 Correct 256 ms 78960 KB Output is correct
35 Correct 243 ms 78812 KB Output is correct
36 Correct 389 ms 79096 KB Output is correct
37 Correct 286 ms 79144 KB Output is correct
38 Correct 313 ms 78812 KB Output is correct
39 Correct 232 ms 78836 KB Output is correct
40 Correct 318 ms 79176 KB Output is correct
41 Correct 232 ms 79012 KB Output is correct
42 Correct 358 ms 78900 KB Output is correct