Submission #155766

#	Time	Username	Problem	Language	Result	Execution time	Memory
155766		shuvi_dola	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	438 ms	79340 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 4;
const int N = 1e7 + 3;
const int inf = 1e9;
int p[M], dp[N], d[N];
int m, q;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> m >> q;
	for(int i = 1; i <= m; i++)
	{
		cin >> p[i];
	}

	for(int i = 1; i <= m; i++)
	{
		int j = p[i];
		while(j < N)
		{
			d[j] = max(d[j], p[i]);
			j += p[i];
			
		}
	}
	d[0] = p[m];
	int j = 0;
	for(int i = 1; i < N; i++)
	{
		while(j + d[j] - 1 < i)
		{
			j++;
		}
		// if(i <= 5)
			// cout << i << ' ' << j << '\n';
		if(j >= i)
			dp[i] = inf;
		dp[i] = dp[j] + 1;

	}
	while(q--)
	{
		int x;
		cin >> x;
		if(dp[x] >= inf)
			cout << "oo\n";
		else
			cout << dp[x] << '\n';
	}
}

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