Submission #163972

#	Time	Username	Problem	Language	Result	Execution time	Memory
163972		luciocf	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	8.10 / 100	476 ms	41476 KiB

brunhilda

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int maxv = 1e7+10;
const int inf = 1e9+10;

int a[maxn];

int dp[maxv];

int main(void)
{
	int n, q;
	scanf("%d %d", &n, &q);

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	int P = a[n];
	long long prod = 1ll;

	for (int i = 1; i <= n; i++)
		if (prod < maxv)
			prod = 1ll*prod*a[i];

	for (int i = 1; i < maxv; i++)
		dp[i] = inf;

	dp[1] = 1;
	for (int i = 2; i < maxv; i++)
	{
		if (i%prod == 0) continue;

		if ((i-1)%prod == 0)
		{
			for (int j = n; j >= 1; j--)
				if (i%a[j])
					dp[i] = min(dp[i], dp[i-(i%a[j])]);
		}
		else if (i%P == 0 || (i-1)%P == 0) dp[i] = dp[i-1]+1;
		else dp[i] = dp[i-1];
	}

	for (int i = 1; i <= q; i++)
	{
		int x;
		scanf("%d", &x);

		if (dp[x] == inf) printf("oo\n");
		else printf("%d\n", dp[x]);
	}
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
brunhilda.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
brunhilda.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

• Subtask 1: 1.1111111111111112 / 20
• Subtask 2: 5.555555555555555 / 20
• Subtask 3: 1.4285714285714286 / 60