Submission #155734

#	Time	Username	Problem	Language	Result	Execution time	Memory
155734		shuvi_dola	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	17.78 / 100	1107 ms	262148 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;;
const int lim = 1e7 + 3;
const int inf = 1e9 + 9;
int p[N], m, q;
int dp[lim];
string s;
int dfs(int u)
{
	if(dp[u] != inf)
		return dp[u];

	if(u == 0)
		return 0;
	int cnt = 0;
	for(int i = 1; i <= m; i++)
	{
		
		if(u % p[i] == 0 && u != 0)
		{
			cnt ++;
			continue;
		}

		dp[u] = min(dp[u], dfs(u - u % p[i]) + 1);
	}
	if(cnt == m)
	{
		dp[u] = inf - 1;
		return inf - 1;
	}

	return dp[u];
}

int main()
{
	for(int i = 1; i < lim; i++)
	{
		dp[i] = inf;
	}
	cin >> m >> q;
	for(int i = 1; i <= m; i++)
	{
		cin >> p[i];
	}
	sort(p + 1, p + 1 + m);
	for(int i = 1; i <= q; i++)
	{
		int n;
		cin >> n;
		dfs(n);
		if(dp[n] == inf - 1)
			cout << "oo\n";
		else
			cout << dp[n] << '\n';
	}
}

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