Submission #31866

#	Time	Username	Problem	Language	Result	Execution time	Memory
31866		huynd2001	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	62.86 / 100	656 ms	80532 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 main()
{
	int n,q;
	cin >> n >> q;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	int maxo=10000007;
	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;
		}
		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++)
	{
		int b;
		cin >> b;
		if(dp[b]>=maxo) cout << "oo\n"; else cout << dp[b] << "\n";
	}
	return 0;
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:40:30: warning: iteration 10000004u invokes undefined behavior [-Waggressive-loop-optimizations]
   dp[i]=min(dp[curl]+1,dp[i]);
                              ^
brunhilda.cpp:33:15: note: containing loop
  for(int i=1;i<=maxo;i++)
               ^
brunhilda.cpp:23:35: warning: iteration 10000004u invokes undefined behavior [-Waggressive-loop-optimizations]
  for(int i=1;i<=maxo;i++) dp[i]=oo;
                                   ^
brunhilda.cpp:23:15: note: containing loop
  for(int i=1;i<=maxo;i++) dp[i]=oo;
               ^

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 22.857142857142858 / 60