Submission #334745

#	Time	Username	Problem	Language	Result	Execution time	Memory
334745		Fischer	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	372 ms	95084 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1.2e7 + 10;
int dp[maxn];
int link[maxn];

int main() {
	int m, q;
	scanf("%d%d", &m, &q);
	for (int i=0; i<m; ++i) {
		int x;
		scanf("%d", &x);
		for (int j=x-1; j<maxn; j+=x) {
			link[j] = x-1;
		}
	}
	for (int i = maxn-2; i >= 1; --i) {
		if (link[i] < link[i+1] - 1) {
			link[i] = link[i+1] - 1;
		}
	}
	const int inf = 1e9;
	for (int i = 1; i < maxn; ++i) {
			if (link[i] == 0) dp[i] = inf;
			else dp[i] = min(inf, dp[i - link[i]] + 1);
	}
	while (q--) {
		int n;
		scanf("%d", &n);
		if (dp[n] > n) puts("oo\n");
		else printf("%d\n", dp[n]);
	}
	return 0;
}

Compilation message (stderr)

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

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