oj.uz

답안 #230232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230232 2020-05-09T09:17:17 Z kshitij_sodani Brunhilda’s Birthday (BOI13_brunhilda) C++17
77.4603 / 100
 783 ms 235896 KB 
#include <iostream>	
#include <bits/stdc++.h>	
using namespace std;	
typedef int64_t llo;	
#define mp make_pair	
#define pb push_back	
#define a first	
#define b second
#define endl '\n'	
int ma[30000001];

int dp[30000001];
//vector<int> fac[30000001];
int main(){	
	memset(ma,0,sizeof(ma));
	ios_base::sync_with_stdio(false);	
	cin.tie(NULL);
	int n,s;
	cin>>n>>s;
	int aa;
	int it[n];
	for(int i=0;i<n;i++){
		cin>>it[i];
	}
	sort(it,it+n);
	for(int i=0;i<n;i++){
		for(int j=it[i];j<30000001;j+=it[i]){
			ma[j-1]=it[i]-1;
		}
	}
	for(int i=10000000-1;i>=0;i--){
		ma[i]=max(ma[i],ma[i+1]-1);
	}
	dp[0]=0;
	for(int j=1;j<30000001;j++){
		if(ma[j]==0){
			dp[j]=-1;
		}
		else if(dp[j-ma[j]]!=-1){
			dp[j]=dp[j-ma[j]]+1;
		}
		else{
			dp[j]=-1;
		}
	}


	while(s--){
		cin>>aa;
		if(dp[aa]==-1){
			cout<<"oo"<<endl;
		}
		else{
			cout<<dp[aa]<<endl;
		}
	}




	

	return 0;	
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 235128 KB Output is correct
2 Correct 280 ms 235212 KB Output is correct
3 Correct 254 ms 235384 KB Output is correct
4 Correct 222 ms 235128 KB Output is correct
5 Correct 291 ms 235256 KB Output is correct
6 Correct 225 ms 235256 KB Output is correct
7 Correct 247 ms 235128 KB Output is correct
8 Correct 259 ms 235132 KB Output is correct
9 Correct 318 ms 235256 KB Output is correct
10 Correct 360 ms 235128 KB Output is correct
11 Correct 365 ms 235256 KB Output is correct
12 Correct 208 ms 235128 KB Output is correct
13 Correct 544 ms 235256 KB Output is correct
14 Correct 546 ms 235128 KB Output is correct
15 Correct 306 ms 235128 KB Output is correct
16 Correct 273 ms 235208 KB Output is correct
17 Correct 309 ms 235360 KB Output is correct
18 Correct 217 ms 235256 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 286 ms 235256 KB Output is correct
2 Correct 339 ms 235640 KB Output is correct
3 Correct 689 ms 235456 KB Output is correct
4 Correct 368 ms 235128 KB Output is correct
5 Correct 546 ms 235512 KB Output is correct
6 Correct 282 ms 235208 KB Output is correct
7 Correct 275 ms 235256 KB Output is correct
8 Correct 375 ms 235128 KB Output is correct
9 Correct 603 ms 235512 KB Output is correct
10 Correct 720 ms 235640 KB Output is correct
11 Incorrect 697 ms 235384 KB Output isn't correct
12 Correct 432 ms 235256 KB Output is correct
13 Correct 253 ms 235128 KB Output is correct
14 Correct 377 ms 235256 KB Output is correct
15 Correct 573 ms 235340 KB Output is correct
16 Correct 325 ms 235512 KB Output is correct
17 Correct 585 ms 235256 KB Output is correct
18 Correct 621 ms 235512 KB Output is correct

Subtask #3
38.5714285714 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 590 ms 235568 KB Output is correct
2 Correct 726 ms 235384 KB Output is correct
3 Correct 718 ms 235640 KB Output is correct
4 Incorrect 459 ms 235384 KB Output isn't correct
5 Incorrect 380 ms 235768 KB Output isn't correct
6 Correct 587 ms 235516 KB Output is correct
7 Correct 583 ms 235640 KB Output is correct
8 Correct 588 ms 235384 KB Output is correct
9 Correct 604 ms 235512 KB Output is correct
10 Correct 523 ms 235256 KB Output is correct
11 Incorrect 477 ms 235256 KB Output isn't correct
12 Correct 541 ms 235336 KB Output is correct
13 Correct 676 ms 235640 KB Output is correct
14 Correct 406 ms 235768 KB Output is correct
15 Incorrect 576 ms 235324 KB Output isn't correct
16 Correct 629 ms 235256 KB Output is correct
17 Correct 578 ms 235384 KB Output is correct
18 Correct 707 ms 235512 KB Output is correct
19 Incorrect 269 ms 235256 KB Output isn't correct
20 Correct 724 ms 235528 KB Output is correct
21 Incorrect 444 ms 235896 KB Output isn't correct
22 Correct 745 ms 235768 KB Output is correct
23 Correct 380 ms 235472 KB Output is correct
24 Correct 299 ms 235512 KB Output is correct
25 Incorrect 510 ms 235640 KB Output isn't correct
26 Incorrect 463 ms 235512 KB Output isn't correct
27 Correct 773 ms 235768 KB Output is correct
28 Incorrect 306 ms 235512 KB Output isn't correct
29 Correct 733 ms 235820 KB Output is correct
30 Correct 649 ms 235768 KB Output is correct
31 Correct 376 ms 235376 KB Output is correct
32 Incorrect 411 ms 235848 KB Output isn't correct
33 Incorrect 257 ms 235384 KB Output isn't correct
34 Correct 593 ms 235768 KB Output is correct
35 Incorrect 334 ms 235512 KB Output isn't correct
36 Correct 783 ms 235740 KB Output is correct
37 Incorrect 377 ms 235896 KB Output isn't correct
38 Correct 591 ms 235640 KB Output is correct
39 Incorrect 342 ms 235512 KB Output isn't correct
40 Correct 519 ms 235512 KB Output is correct
41 Correct 518 ms 235640 KB Output is correct
42 Incorrect 622 ms 235640 KB Output isn't correct