Submission #66183

#	Time	Username	Problem	Language	Result	Execution time	Memory
66183		MatheusLealV	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	20 / 100	62 ms	3888 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 < N; j+= p[i]) pr[j] = p[i];
	}

	pr[0] = p[n];

	dp[0] = 1;

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

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

		lim = max(lim, min(N, 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: 0 / 20
• Subtask 3: 0 / 60