oj.uz

답안 #631363

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631363 2022-08-18T03:46:33 Z uylulu Brunhilda’s Birthday (BOI13_brunhilda) C++14
24.7619 / 100
 395 ms 159904 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 < 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 30 ms 39404 KB Output is correct
2 Runtime error 154 ms 159100 KB Execution killed with signal 11
3 Correct 41 ms 40460 KB Output is correct
4 Runtime error 132 ms 159064 KB Execution killed with signal 11
5 Correct 74 ms 78484 KB Output is correct
6 Correct 32 ms 39396 KB Output is correct
7 Correct 45 ms 40448 KB Output is correct
8 Correct 52 ms 42900 KB Output is correct
9 Runtime error 167 ms 158992 KB Execution killed with signal 11
10 Runtime error 191 ms 159148 KB Execution killed with signal 11
11 Correct 132 ms 78464 KB Output is correct
12 Runtime error 137 ms 159112 KB Execution killed with signal 11
13 Runtime error 254 ms 159028 KB Execution killed with signal 11
14 Runtime error 304 ms 159184 KB Execution killed with signal 11
15 Correct 86 ms 78468 KB Output is correct
16 Runtime error 165 ms 159048 KB Execution killed with signal 11
17 Runtime error 172 ms 159096 KB Execution killed with signal 11
18 Runtime error 128 ms 159048 KB Execution killed with signal 11

Subtask #2
4.44444444444 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 157 ms 159200 KB Execution killed with signal 11
2 Correct 107 ms 78912 KB Output is correct
3 Runtime error 291 ms 159660 KB Execution killed with signal 11
4 Runtime error 158 ms 159084 KB Execution killed with signal 11
5 Runtime error 269 ms 159436 KB Execution killed with signal 11
6 Correct 83 ms 78452 KB Output is correct
7 Runtime error 140 ms 159196 KB Execution killed with signal 11
8 Runtime error 156 ms 159088 KB Execution killed with signal 11
9 Runtime error 284 ms 159584 KB Execution killed with signal 11
10 Runtime error 306 ms 159636 KB Execution killed with signal 11
11 Runtime error 291 ms 159636 KB Execution killed with signal 11
12 Runtime error 185 ms 159012 KB Execution killed with signal 11
13 Runtime error 136 ms 159144 KB Execution killed with signal 11
14 Runtime error 154 ms 159044 KB Execution killed with signal 11
15 Runtime error 248 ms 159396 KB Execution killed with signal 11
16 Correct 102 ms 78808 KB Output is correct
17 Runtime error 248 ms 159032 KB Execution killed with signal 11
18 Correct 189 ms 78900 KB Output is correct

Subtask #3
11.4285714286 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 263 ms 159440 KB Execution killed with signal 11
2 Runtime error 294 ms 159440 KB Execution killed with signal 11
3 Runtime error 344 ms 159448 KB Execution killed with signal 11
4 Correct 328 ms 78808 KB Output is correct
5 Runtime error 185 ms 159852 KB Execution killed with signal 11
6 Runtime error 295 ms 159092 KB Execution killed with signal 11
7 Runtime error 293 ms 159828 KB Execution killed with signal 11
8 Runtime error 302 ms 159468 KB Execution killed with signal 11
9 Runtime error 328 ms 159428 KB Execution killed with signal 11
10 Correct 172 ms 78496 KB Output is correct
11 Runtime error 219 ms 159080 KB Execution killed with signal 11
12 Runtime error 290 ms 159052 KB Execution killed with signal 11
13 Runtime error 300 ms 159228 KB Execution killed with signal 11
14 Runtime error 217 ms 159104 KB Execution killed with signal 11
15 Runtime error 264 ms 159136 KB Execution killed with signal 11
16 Runtime error 303 ms 159084 KB Execution killed with signal 11
17 Runtime error 335 ms 159408 KB Execution killed with signal 11
18 Runtime error 342 ms 159444 KB Execution killed with signal 11
19 Runtime error 165 ms 159056 KB Execution killed with signal 11
20 Runtime error 341 ms 159492 KB Execution killed with signal 11
21 Runtime error 226 ms 159092 KB Execution killed with signal 11
22 Runtime error 356 ms 159880 KB Execution killed with signal 11
23 Runtime error 214 ms 159344 KB Execution killed with signal 11
24 Correct 279 ms 78820 KB Output is correct
25 Runtime error 279 ms 159120 KB Execution killed with signal 11
26 Correct 374 ms 78784 KB Output is correct
27 Runtime error 363 ms 159868 KB Execution killed with signal 11
28 Correct 228 ms 78900 KB Output is correct
29 Runtime error 291 ms 159852 KB Execution killed with signal 11
30 Runtime error 290 ms 159612 KB Execution killed with signal 11
31 Runtime error 153 ms 159060 KB Execution killed with signal 11
32 Correct 243 ms 78884 KB Output is correct
33 Runtime error 135 ms 159052 KB Execution killed with signal 11
34 Runtime error 300 ms 159904 KB Execution killed with signal 11
35 Runtime error 144 ms 159124 KB Execution killed with signal 11
36 Correct 395 ms 79180 KB Output is correct
37 Runtime error 203 ms 159844 KB Execution killed with signal 11
38 Runtime error 246 ms 159124 KB Execution killed with signal 11
39 Runtime error 145 ms 159052 KB Execution killed with signal 11
40 Runtime error 230 ms 159156 KB Execution killed with signal 11
41 Correct 228 ms 78956 KB Output is correct
42 Runtime error 273 ms 159116 KB Execution killed with signal 11