Submission #87783

#	Time	Username	Problem	Language	Result	Execution time	Memory
87783		JustInCase	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	553 ms	44272 KiB

brunhilda

#include <bits/stdc++.h>

const int32_t MAX_N = 1e7 + 1e6;

int32_t dp[MAX_N + 5];

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int32_t m, q;
	std::cin >> m >> q;

	int64_t lcm = 1;
	for(int32_t i = 0; i < m; i++) {
		int32_t p;
		std::cin >> p;

		for(int32_t j = p - 1; j <= MAX_N; j += p) {
			dp[j] = p - 1;
		}

		if(lcm < MAX_N) {
			lcm *= (int64_t) p;
		}
	}

	for(int32_t i = MAX_N - 1; i >= 1; i--) {
		dp[i] = std::max(dp[i], dp[i + 1] - 1);
	}

	dp[0] = 0;
	for(int32_t i = 1; i <= MAX_N; i++) {
		dp[i] = dp[i - dp[i]] + 1;
	}

	for(int32_t i = 0; i < q; i++) {
		int32_t n;
		std::cin >> n;

		if(n >= lcm) {
			std::cout << "oo" << '\n';
		}
		else {
			std::cout << dp[n] << '\n';
		}
	}
}

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