101572024-03-28 19:45:07111Az óvodai lét elviselhetetlen könnyűsége #2cpp17Wrong answer 30/100115ms6472 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define MA (int)1e4

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
1Accepted29ms2032 KiB
2Accepted72ms2300 KiB
subtask220/20
3Accepted32ms2560 KiB
4Accepted35ms2768 KiB
5Accepted35ms2876 KiB
6Accepted4ms3140 KiB
7Accepted6ms3400 KiB
8Accepted14ms3608 KiB
9Accepted16ms3704 KiB
10Accepted30ms3848 KiB
subtask310/10
11Accepted59ms3832 KiB
12Accepted78ms4068 KiB
13Accepted85ms4272 KiB
14Accepted65ms4272 KiB
15Accepted48ms4520 KiB
16Accepted82ms4492 KiB
17Accepted54ms6008 KiB
subtask40/15
18Accepted45ms4568 KiB
19Accepted37ms4320 KiB
20Wrong answer41ms5556 KiB
21Accepted28ms4456 KiB
22Wrong answer115ms6080 KiB
23Accepted85ms4516 KiB
24Accepted85ms4516 KiB
25Accepted86ms4516 KiB
26Wrong answer32ms4784 KiB
27Accepted64ms5196 KiB
subtask50/55
28Wrong answer67ms6012 KiB
29Wrong answer65ms6036 KiB
30Wrong answer67ms4888 KiB
31Wrong answer61ms4804 KiB
32Wrong answer63ms5052 KiB
33Wrong answer50ms5096 KiB
34Accepted75ms4944 KiB
35Accepted107ms4952 KiB
36Wrong answer75ms5068 KiB
37Wrong answer65ms5216 KiB
38Wrong answer71ms5988 KiB
39Wrong answer75ms6472 KiB