oj.uz

답안 #631360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631360 2022-08-18T03:43:35 Z uylulu Brunhilda’s Birthday (BOI13_brunhilda) C++14
24.7619 / 100
 379 ms 159920 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] = 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 <= 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 34 ms 39392 KB Output is correct
2 Runtime error 160 ms 159028 KB Execution killed with signal 11
3 Correct 39 ms 40460 KB Output is correct
4 Runtime error 135 ms 159052 KB Execution killed with signal 11
5 Correct 84 ms 78464 KB Output is correct
6 Correct 36 ms 39508 KB Output is correct
7 Correct 43 ms 40400 KB Output is correct
8 Correct 46 ms 42968 KB Output is correct
9 Runtime error 185 ms 159068 KB Execution killed with signal 11
10 Runtime error 190 ms 159116 KB Execution killed with signal 11
11 Correct 100 ms 78468 KB Output is correct
12 Runtime error 131 ms 159112 KB Execution killed with signal 11
13 Runtime error 256 ms 159052 KB Execution killed with signal 11
14 Runtime error 255 ms 159096 KB Execution killed with signal 11
15 Correct 86 ms 78452 KB Output is correct
16 Runtime error 173 ms 159060 KB Execution killed with signal 11
17 Runtime error 151 ms 159108 KB Execution killed with signal 11
18 Runtime error 138 ms 159020 KB Execution killed with signal 11

Subtask #2
4.44444444444 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 153 ms 159160 KB Execution killed with signal 11
2 Correct 100 ms 78848 KB Output is correct
3 Runtime error 301 ms 159680 KB Execution killed with signal 11
4 Runtime error 167 ms 159052 KB Execution killed with signal 11
5 Runtime error 232 ms 159436 KB Execution killed with signal 11
6 Correct 92 ms 78468 KB Output is correct
7 Runtime error 143 ms 159164 KB Execution killed with signal 11
8 Runtime error 164 ms 159044 KB Execution killed with signal 11
9 Runtime error 264 ms 159636 KB Execution killed with signal 11
10 Runtime error 309 ms 159616 KB Execution killed with signal 11
11 Runtime error 296 ms 159516 KB Execution killed with signal 11
12 Runtime error 184 ms 159112 KB Execution killed with signal 11
13 Runtime error 132 ms 159104 KB Execution killed with signal 11
14 Runtime error 173 ms 159112 KB Execution killed with signal 11
15 Runtime error 248 ms 159400 KB Execution killed with signal 11
16 Correct 95 ms 78868 KB Output is correct
17 Runtime error 255 ms 159044 KB Execution killed with signal 11
18 Correct 185 ms 78856 KB Output is correct

Subtask #3
11.4285714286 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 274 ms 159432 KB Execution killed with signal 11
2 Runtime error 332 ms 159472 KB Execution killed with signal 11
3 Runtime error 293 ms 159480 KB Execution killed with signal 11
4 Correct 258 ms 78832 KB Output is correct
5 Runtime error 177 ms 159888 KB Execution killed with signal 11
6 Runtime error 250 ms 159112 KB Execution killed with signal 11
7 Runtime error 259 ms 159920 KB Execution killed with signal 11
8 Runtime error 245 ms 159420 KB Execution killed with signal 11
9 Runtime error 255 ms 159424 KB Execution killed with signal 11
10 Correct 160 ms 78496 KB Output is correct
11 Runtime error 183 ms 159044 KB Execution killed with signal 11
12 Runtime error 244 ms 159072 KB Execution killed with signal 11
13 Runtime error 293 ms 159348 KB Execution killed with signal 11
14 Runtime error 189 ms 159104 KB Execution killed with signal 11
15 Runtime error 231 ms 159144 KB Execution killed with signal 11
16 Runtime error 261 ms 159104 KB Execution killed with signal 11
17 Runtime error 259 ms 159416 KB Execution killed with signal 11
18 Runtime error 328 ms 159548 KB Execution killed with signal 11
19 Runtime error 146 ms 159056 KB Execution killed with signal 11
20 Runtime error 315 ms 159432 KB Execution killed with signal 11
21 Runtime error 227 ms 159064 KB Execution killed with signal 11
22 Runtime error 303 ms 159876 KB Execution killed with signal 11
23 Runtime error 205 ms 159252 KB Execution killed with signal 11
24 Correct 210 ms 78804 KB Output is correct
25 Runtime error 215 ms 159024 KB Execution killed with signal 11
26 Correct 263 ms 78896 KB Output is correct
27 Runtime error 316 ms 159856 KB Execution killed with signal 11
28 Correct 235 ms 78824 KB Output is correct
29 Runtime error 294 ms 159884 KB Execution killed with signal 11
30 Runtime error 258 ms 159560 KB Execution killed with signal 11
31 Runtime error 164 ms 159052 KB Execution killed with signal 11
32 Correct 253 ms 78784 KB Output is correct
33 Runtime error 136 ms 159124 KB Execution killed with signal 11
34 Runtime error 250 ms 159880 KB Execution killed with signal 11
35 Runtime error 147 ms 159132 KB Execution killed with signal 11
36 Correct 379 ms 79080 KB Output is correct
37 Runtime error 176 ms 159820 KB Execution killed with signal 11
38 Runtime error 232 ms 159088 KB Execution killed with signal 11
39 Runtime error 144 ms 159112 KB Execution killed with signal 11
40 Runtime error 209 ms 159100 KB Execution killed with signal 11
41 Correct 235 ms 79056 KB Output is correct
42 Runtime error 250 ms 159128 KB Execution killed with signal 11