Submission #36499

#	Time	Username	Problem	Language	Result	Execution time	Memory
36499		cheater2k	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	20 / 100	29 ms	9988 KiB

brunhilda

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

const int MAX = 1000000;
const int inf = 1e9 + 10;

int nprime, nquery;
int maxdiv[MAX + 5];
int dp[MAX + 5];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> nprime >> nquery;
	for (int i = 1; i <= MAX; ++i) dp[i] = inf;
	for (int i = 1; i <= nprime; ++i) {
		int p; cin >> p;
		for (int j = 0; j <= MAX; j += p) maxdiv[j] = p;
	}
	
	int cur = 0;
	for (int i = 1; i <= MAX; ++i) {
		while(cur < i) {
			if (!maxdiv[cur] || cur + maxdiv[cur] <= i) ++cur;
			else break;
		}
		if (cur == i) continue;
		dp[i] = min(dp[i], dp[cur] + 1);
	}

	while(nquery--) {
		int n; cin >> n;
		if (dp[n] != inf) printf("%d\n", dp[n]);
		else printf("oo\n");
	}
}

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