제출 #155735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
155735		shuvi_dola	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	21.43 / 100	1092 ms	42672 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 = m; i >= 1; i--)
	{
		if(p[i] > u)
		{
			dp[u] = 1;
			return dp[u];
		}
		
		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: 2.2222222222222223 / 20
• Subtask 3: 1.4285714285714286 / 60