Submission #1126176

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

brunhilda

#include <bits/stdc++.h>
 
using namespace std;
 
int n, q;
 
vector <int> a, dp(10000000, -1);
 
int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);
 
	cin >> n >> q;
	a.resize(n+1);
	long long s = 1;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(s > 1e7) continue;
		s *= a[i];
	}
	dp[0] = 0;
	for(int i = 1; i <= (1e7)/n; i++){
		int k = 0;
		for(int j = 1; j <= n; j++){
			k = max(k, (i%a[j]));
		}
		if(k == 0) continue;
		dp[i] = dp[i-k] + 1;
	}
	while(q--){
		int x;
		cin >> x;
		if(x >= s) cout << "oo\n";
		else cout << dp[x] << "\n";
	}
}

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