Submission #66185

#	Time	Username	Problem	Language	Result	Execution time	Memory
66185		MatheusLealV	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	419 ms	80024 KiB

brunhilda

#include <bits/stdc++.h>
#define N 100050
using namespace std;

int n, q, p[N], dp[10000005], prox[10000005], pr[N], lim;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>q;

	for(int i = 1; i <= n; i++)
	{
		cin>>p[i];

		for(int j = p[i]; j < 10000005; j+= p[i]) pr[j] = p[i];
	}

	pr[0] = p[n];

	dp[0] = 1;

	for(int i = 0; i < 10000005; i++)
	{
		if(!dp[i]) continue;

		for(int j = lim + 1; j < min(10000005, i + pr[i]); j++) dp[j] = dp[i] + 1;

		lim = max(lim, min(10000005, i + pr[i]) - 1);
	}

	for(int i = 1, x; i <= q; i++)
	{
		cin>>x;

		if(!dp[x]) cout<<"oo\n";

		else cout<<dp[x] - 1<<"\n";
	}
}

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