Submission #444921

#	Time	Username	Problem	Language	Result	Execution time	Memory
444921		aryan12	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	337 ms	81856 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
 
const int N = 1e7 + 1e5;
int dp[N];
 
void Solve() {
	for(int i = 0; i < N; i++) {
		dp[i] = 0;
	}
	int m, q;
	cin >> m >> q;
	int primes[m + 1];
	int lcm = 1;
	for(int i = 1; i <= m; i++) {
		cin >> primes[i];
		lcm *= primes[i];
		lcm = min(lcm, N + 10);
		for(int j = primes[i] - 1; j < N; j += primes[i]) {
			dp[j] = primes[i] - 1;
		}
	}
	for(int i = N - 2; i >= 0; i--) {
		dp[i] = max(dp[i], dp[i + 1] - 1);
	}
	for(int i = 1; i < N; i++) {
		if(i >= lcm) {
			dp[i] = -1;
			continue;
		}
		dp[i] = dp[i - dp[i]] + 1;
	}
	while(q--) {
		int num;
		cin >> num;
		if(dp[num] == -1) {
			cout << "oo\n";
		}
		else {
			cout << dp[num] << "\n";
		}
	}
}
 
int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

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