101582024-03-28 19:45:50111Az óvodai lét elviselhetetlen könnyűsége #2cpp17Time limit exceeded 0/1001.582s5736 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define MA (int)1e5

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int M,Q;
	cin>>M>>Q;
	vector<int>v(M);
	for(int i=0;i<M;i++){
		cin>>v[i];
	}
	sort(v.rbegin(),v.rend());
	vector<int>dp(MA);
	dp[0]=1;
	for(int i=1;i<MA;i++){
		int h=0;
		for(int j=0;j<M&&v[j]>h;j++){
			h=max(h,dp[i-1]*(v[j]-1)%v[j]);
		}
		dp[i]=dp[i-1]+h;
		if(h==0||dp[i]>1e7){
			fill(dp.begin()+i,dp.end(),dp[i-1]);
		}
	}
	while(Q--){
		int N;
		cin>>N;
		int l=0,h=MA;
		while(l<h){
			int m=(l+h)/2;
			if(dp[m]>N){
				h=m;
			}
			else{
				l=m+1;
			}
		}
		cout<<(h==MA?0:h)<<'\n';
	}
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Time limit exceeded1.562s1992 KiB
2Time limit exceeded1.582s2148 KiB
subtask20/20
3Time limit exceeded1.547s2228 KiB
4Time limit exceeded1.565s2584 KiB
5Time limit exceeded1.539s2980 KiB
6Accepted17ms4380 KiB
7Time limit exceeded1.521s2836 KiB
8Time limit exceeded1.55s2888 KiB
9Time limit exceeded1.574s2884 KiB
10Time limit exceeded1.554s2952 KiB
subtask30/10
11Time limit exceeded1.565s3188 KiB
12Time limit exceeded1.574s3560 KiB
13Time limit exceeded1.575s3448 KiB
14Time limit exceeded1.57s3584 KiB
15Time limit exceeded1.562s3652 KiB
16Time limit exceeded1.567s3576 KiB
17Time limit exceeded1.57s4320 KiB
subtask40/15
18Time limit exceeded1.57s3496 KiB
19Time limit exceeded1.562s3760 KiB
20Time limit exceeded1.549s4516 KiB
21Time limit exceeded1.582s3796 KiB
22Time limit exceeded1.559s4444 KiB
23Time limit exceeded1.574s3992 KiB
24Time limit exceeded1.554s4004 KiB
25Time limit exceeded1.57s4328 KiB
26Time limit exceeded1.567s4288 KiB
27Time limit exceeded1.565s4884 KiB
subtask50/55
28Time limit exceeded1.562s5112 KiB
29Time limit exceeded1.57s5416 KiB
30Time limit exceeded1.534s4592 KiB
31Time limit exceeded1.557s4584 KiB
32Time limit exceeded1.546s4628 KiB
33Time limit exceeded1.562s4640 KiB
34Time limit exceeded1.562s4612 KiB
35Time limit exceeded1.549s4676 KiB
36Time limit exceeded1.574s4812 KiB
37Time limit exceeded1.574s4932 KiB
38Time limit exceeded1.562s5548 KiB
39Time limit exceeded1.547s5736 KiB