Submission #1126247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126247		Muhammet	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	100 / 100	255 ms	79272 KiB

brunhilda

#include <bits/stdc++.h>
 
using namespace std;
 
const int M = 1e7;

int n, q, a[100005], b[M+1], dp[M+1];

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);
 
	cin >> n >> q;
	long long s = 1;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		for(int j = a[i]-1; j <= M; j += a[i]){
			b[j] = max(b[j], a[i]-1);
		}
		b[M] = max(b[M], M%a[i]);
		if(s > 1e7) continue;
		s *= a[i];
	}
	for(int i = M-1; i >= 1; i--){
		b[i] = max(b[i], b[i+1]-1);
	}
	dp[0] = 0;
	for(int i = 1; i <= M; i++){
		dp[i] = dp[i-b[i]] + 1;
	}
	while(q--){
		int x;
		cin >> x;
		if(x >= s) cout << "oo\n";
		else cout << dp[x] << "\n";
	}
}

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