답안 #31870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31870	2017-09-11T08:18:36 Z	huynd2001	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	519 ms	80920 KB

brunhilda

/*huypheu
2 2
2 3
5
6
*/
#include <bits/stdc++.h>
#define oo (INT_MAX/2)
using namespace std;

int pri[10000005],dp[10000005];
int a[100005];
int b[100005];

int main()
{
	int n,q;
	cin >> n >> q;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	int maxo=0;
	for(int i=1;i<=q;i++)
	{
		cin >> b[i];
		maxo=max(maxo,b[i]);
	}
	for(int i=1;i<=maxo;i++) dp[i]=oo;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=(maxo/a[i]);j++)
		{
			pri[a[i]*j]=a[i];
		}
	}
	dp[0]=0;
	int curl=0,curr=0+pri[0]-1;
	for(int i=1;i<=maxo;i++)
	{
		while(i>curr)
		{
			curl++;
			curr=curl+pri[curl]-1;
		}
		if(curl==i) break;
		dp[i]=min(dp[curl]+1,dp[i]);
	}
	// for(int i=1;i<=10;i++)
	// {
	// 	cout << dp[i] << " ";	
	// }
	// cout << endl;
	for(int i=1;i<=q;i++)
	{
		if(dp[b[i]]>=maxo) cout << "oo\n"; else cout << dp[b[i]] << "\n";
	}
	return 0;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	80920 KB	Output is correct
2	Correct	0 ms	80920 KB	Output is correct
3	Correct	0 ms	80920 KB	Output is correct
4	Correct	6 ms	80920 KB	Output is correct
5	Correct	0 ms	80920 KB	Output is correct
6	Correct	0 ms	80920 KB	Output is correct
7	Correct	0 ms	80920 KB	Output is correct
8	Correct	0 ms	80920 KB	Output is correct
9	Correct	0 ms	80920 KB	Output is correct
10	Correct	0 ms	80920 KB	Output is correct
11	Correct	0 ms	80920 KB	Output is correct
12	Correct	0 ms	80920 KB	Output is correct
13	Correct	0 ms	80920 KB	Output is correct
14	Correct	0 ms	80920 KB	Output is correct
15	Correct	0 ms	80920 KB	Output is correct
16	Correct	0 ms	80920 KB	Output is correct
17	Correct	6 ms	80920 KB	Output is correct
18	Correct	3 ms	80920 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	80920 KB	Output is correct
2	Correct	116 ms	80920 KB	Output is correct
3	Correct	169 ms	80920 KB	Output is correct
4	Correct	89 ms	80920 KB	Output is correct
5	Correct	43 ms	80920 KB	Output is correct
6	Correct	19 ms	80920 KB	Output is correct
7	Correct	73 ms	80920 KB	Output is correct
8	Correct	36 ms	80920 KB	Output is correct
9	Correct	73 ms	80920 KB	Output is correct
10	Correct	169 ms	80920 KB	Output is correct
11	Correct	383 ms	80920 KB	Output is correct
12	Correct	146 ms	80920 KB	Output is correct
13	Correct	56 ms	80920 KB	Output is correct
14	Correct	99 ms	80920 KB	Output is correct
15	Correct	63 ms	80920 KB	Output is correct
16	Correct	113 ms	80920 KB	Output is correct
17	Correct	303 ms	80920 KB	Output is correct
18	Correct	306 ms	80920 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	336 ms	80920 KB	Output is correct
2	Correct	413 ms	80920 KB	Output is correct
3	Correct	299 ms	80920 KB	Output is correct
4	Correct	249 ms	80920 KB	Output is correct
5	Correct	226 ms	80920 KB	Output is correct
6	Correct	329 ms	80920 KB	Output is correct
7	Correct	226 ms	80920 KB	Output is correct
8	Correct	283 ms	80920 KB	Output is correct
9	Correct	303 ms	80920 KB	Output is correct
10	Correct	226 ms	80920 KB	Output is correct
11	Correct	176 ms	80920 KB	Output is correct
12	Correct	243 ms	80920 KB	Output is correct
13	Correct	206 ms	80920 KB	Output is correct
14	Correct	129 ms	80920 KB	Output is correct
15	Correct	296 ms	80920 KB	Output is correct
16	Correct	313 ms	80920 KB	Output is correct
17	Correct	313 ms	80920 KB	Output is correct
18	Correct	426 ms	80920 KB	Output is correct
19	Correct	106 ms	80920 KB	Output is correct
20	Correct	299 ms	80920 KB	Output is correct
21	Correct	243 ms	80920 KB	Output is correct
22	Correct	493 ms	80920 KB	Output is correct
23	Correct	213 ms	80920 KB	Output is correct
24	Correct	133 ms	80920 KB	Output is correct
25	Correct	306 ms	80920 KB	Output is correct
26	Correct	246 ms	80920 KB	Output is correct
27	Correct	369 ms	80920 KB	Output is correct
28	Correct	136 ms	80920 KB	Output is correct
29	Correct	483 ms	80920 KB	Output is correct
30	Correct	409 ms	80920 KB	Output is correct
31	Correct	183 ms	80920 KB	Output is correct
32	Correct	206 ms	80920 KB	Output is correct
33	Correct	116 ms	80920 KB	Output is correct
34	Correct	243 ms	80920 KB	Output is correct
35	Correct	143 ms	80920 KB	Output is correct
36	Correct	519 ms	80920 KB	Output is correct
37	Correct	203 ms	80920 KB	Output is correct
38	Correct	366 ms	80920 KB	Output is correct
39	Correct	156 ms	80920 KB	Output is correct
40	Correct	289 ms	80920 KB	Output is correct
41	Correct	186 ms	80920 KB	Output is correct
42	Correct	413 ms	80920 KB	Output is correct