Submission #31870

#	Time	Username	Problem	Language	Result	Execution time	Memory
31870		huynd2001	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	519 ms	80920 KiB

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60