101542024-03-28 19:33:02111Az óvodai lét elviselhetetlen könnyűsége #2cpp17Time limit exceeded 0/1001.58s11884 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];
	}
	vector<int>dp(MA);
	dp[0]=1;
	for(int i=1;i<MA;i++){
		int h=0;
		for(int j=0;j<M;j++){
			h=max(h,dp[i-1]*(v[j]-1)%v[j]);
		}
		dp[i]=dp[i-1]+h;
	}
	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
1Accepted6ms3164 KiB
2Accepted301ms4124 KiB
subtask20/20
3Accepted30ms4300 KiB
4Accepted50ms4520 KiB
5Accepted63ms4856 KiB
6Accepted43ms4980 KiB
7Accepted266ms5040 KiB
8Accepted1.312s4964 KiB
9Time limit exceeded1.564s3860 KiB
10Time limit exceeded1.541s3868 KiB
subtask30/10
11Accepted104ms5792 KiB
12Accepted289ms6492 KiB
13Accepted354ms7480 KiB
14Accepted360ms8208 KiB
15Accepted694ms9048 KiB
16Accepted419ms9912 KiB
17Time limit exceeded1.572s9396 KiB
subtask40/15
18Time limit exceeded1.565s8708 KiB
19Time limit exceeded1.575s8760 KiB
20Time limit exceeded1.557s9596 KiB
21Time limit exceeded1.577s8824 KiB
22Time limit exceeded1.57s9556 KiB
23Accepted554ms10160 KiB
24Accepted551ms10156 KiB
25Accepted579ms10160 KiB
26Accepted875ms10420 KiB
27Time limit exceeded1.58s9396 KiB
subtask50/55
28Time limit exceeded1.567s9644 KiB
29Time limit exceeded1.562s9784 KiB
30Time limit exceeded1.578s9084 KiB
31Time limit exceeded1.549s9024 KiB
32Time limit exceeded1.572s8960 KiB
33Time limit exceeded1.562s8948 KiB
34Accepted370ms11176 KiB
35Accepted552ms11884 KiB
36Time limit exceeded1.529s10600 KiB
37Time limit exceeded1.542s10972 KiB
38Time limit exceeded1.554s11360 KiB
39Time limit exceeded1.574s11668 KiB