oj.uz

답안 #631358

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631358 2022-08-18T03:42:01 Z uylulu Brunhilda’s Birthday (BOI13_brunhilda) C++14
24.7619 / 100
 438 ms 160012 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[N + 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] = num[i];
		}
	}
	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 <= lim;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
8.88888888889 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 39436 KB Output is correct
2 Runtime error 147 ms 159060 KB Execution killed with signal 11
3 Correct 30 ms 40456 KB Output is correct
4 Runtime error 139 ms 159072 KB Execution killed with signal 11
5 Correct 83 ms 78540 KB Output is correct
6 Correct 25 ms 39452 KB Output is correct
7 Correct 33 ms 40460 KB Output is correct
8 Correct 35 ms 42956 KB Output is correct
9 Runtime error 185 ms 159112 KB Execution killed with signal 11
10 Runtime error 195 ms 159180 KB Execution killed with signal 11
11 Correct 94 ms 78476 KB Output is correct
12 Runtime error 128 ms 159104 KB Execution killed with signal 11
13 Runtime error 246 ms 159108 KB Execution killed with signal 11
14 Runtime error 221 ms 159100 KB Execution killed with signal 11
15 Correct 74 ms 78460 KB Output is correct
16 Runtime error 159 ms 159216 KB Execution killed with signal 11
17 Runtime error 150 ms 159048 KB Execution killed with signal 11
18 Runtime error 128 ms 159080 KB Execution killed with signal 11

Subtask #2
4.44444444444 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 168 ms 159188 KB Execution killed with signal 11
2 Correct 86 ms 78880 KB Output is correct
3 Runtime error 297 ms 159620 KB Execution killed with signal 11
4 Runtime error 153 ms 159112 KB Execution killed with signal 11
5 Runtime error 208 ms 159436 KB Execution killed with signal 11
6 Correct 76 ms 78540 KB Output is correct
7 Runtime error 155 ms 159252 KB Execution killed with signal 11
8 Runtime error 157 ms 159120 KB Execution killed with signal 11
9 Runtime error 252 ms 159616 KB Execution killed with signal 11
10 Runtime error 266 ms 159604 KB Execution killed with signal 11
11 Runtime error 257 ms 159392 KB Execution killed with signal 11
12 Runtime error 193 ms 159060 KB Execution killed with signal 11
13 Runtime error 151 ms 159064 KB Execution killed with signal 11
14 Runtime error 160 ms 159128 KB Execution killed with signal 11
15 Runtime error 241 ms 159348 KB Execution killed with signal 11
16 Correct 91 ms 78900 KB Output is correct
17 Runtime error 225 ms 159128 KB Execution killed with signal 11
18 Correct 174 ms 78952 KB Output is correct

Subtask #3
11.4285714286 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 228 ms 159528 KB Execution killed with signal 11
2 Runtime error 262 ms 159444 KB Execution killed with signal 11
3 Runtime error 264 ms 159484 KB Execution killed with signal 11
4 Correct 260 ms 78832 KB Output is correct
5 Runtime error 177 ms 159916 KB Execution killed with signal 11
6 Runtime error 249 ms 159108 KB Execution killed with signal 11
7 Runtime error 296 ms 159820 KB Execution killed with signal 11
8 Runtime error 230 ms 159564 KB Execution killed with signal 11
9 Runtime error 268 ms 159412 KB Execution killed with signal 11
10 Correct 156 ms 78612 KB Output is correct
11 Runtime error 179 ms 159156 KB Execution killed with signal 11
12 Runtime error 212 ms 159124 KB Execution killed with signal 11
13 Runtime error 270 ms 159348 KB Execution killed with signal 11
14 Runtime error 184 ms 159000 KB Execution killed with signal 11
15 Runtime error 216 ms 159052 KB Execution killed with signal 11
16 Runtime error 273 ms 159112 KB Execution killed with signal 11
17 Runtime error 243 ms 159404 KB Execution killed with signal 11
18 Runtime error 300 ms 159512 KB Execution killed with signal 11
19 Runtime error 152 ms 159072 KB Execution killed with signal 11
20 Runtime error 285 ms 159416 KB Execution killed with signal 11
21 Runtime error 206 ms 159152 KB Execution killed with signal 11
22 Runtime error 292 ms 159888 KB Execution killed with signal 11
23 Runtime error 158 ms 159308 KB Execution killed with signal 11
24 Correct 218 ms 78796 KB Output is correct
25 Runtime error 205 ms 159124 KB Execution killed with signal 11
26 Correct 257 ms 78744 KB Output is correct
27 Runtime error 294 ms 160012 KB Execution killed with signal 11
28 Correct 253 ms 78868 KB Output is correct
29 Runtime error 282 ms 159860 KB Execution killed with signal 11
30 Runtime error 238 ms 159636 KB Execution killed with signal 11
31 Runtime error 149 ms 159084 KB Execution killed with signal 11
32 Correct 261 ms 78896 KB Output is correct
33 Runtime error 134 ms 159116 KB Execution killed with signal 11
34 Runtime error 243 ms 159884 KB Execution killed with signal 11
35 Runtime error 186 ms 159052 KB Execution killed with signal 11
36 Correct 438 ms 79196 KB Output is correct
37 Runtime error 180 ms 159820 KB Execution killed with signal 11
38 Runtime error 250 ms 159072 KB Execution killed with signal 11
39 Runtime error 151 ms 159052 KB Execution killed with signal 11
40 Runtime error 193 ms 159232 KB Execution killed with signal 11
41 Correct 220 ms 79112 KB Output is correct
42 Runtime error 237 ms 159100 KB Execution killed with signal 11