제출 #1247018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247018		kaiboy	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	100 / 100	187 ms	40092 KiB

brunhilda

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 10000000;

int dp[N + 1];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int k, q; cin >> k >> q;
	while (k--) {
		int p; cin >> p;
		for (int n = p - 1; n < N; n += p)
			dp[n] = max(dp[n], p - 1);
		dp[N] = max(dp[N], N % p);
	}
	for (int n = N - 1; n; n--)
		dp[n] = max(dp[n], dp[n + 1] - 1);
	for (int n = 1; n <= N; n++)
		dp[n] = !dp[n] || dp[n - dp[n]] == -1 ? -1 : dp[n - dp[n]] + 1;
	while (q--) {
		int n; cin >> n;
		if (dp[n] == -1) {
			cout << "oo\n";
			continue;
		}
		cout << dp[n] << '\n';
	}
	return 0;
}

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