10160 2024. 03. 28 19:50:39 111 Az óvodai lét elviselhetetlen könnyűsége #2 cpp17 Elfogadva 100/100 48ms 7576 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());
	int A=1e5;
	vector<int>dp(A);
	dp[0]=1;
	for(int i=1;i<A;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]);
		}
		if(h==0||dp[i-1]>1e7){
			A=i;
		}
		dp[i]=dp[i-1]+h;
	}
	while(Q--){
		int N;
		cin>>N;
		int l=0,h=A;
		while(l<h){
			int m=(l+h)/2;
			if(dp[m]>N){
				h=m;
			}
			else{
				l=m+1;
			}
		}
		cout<<(h==A?0:h)<<'\n';
	}
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 3160 KiB
2 Elfogadva 25ms 3508 KiB
subtask2 20/20
3 Elfogadva 4ms 3728 KiB
4 Elfogadva 4ms 3940 KiB
5 Elfogadva 4ms 4140 KiB
6 Elfogadva 16ms 4336 KiB
7 Elfogadva 9ms 4568 KiB
8 Elfogadva 7ms 4564 KiB
9 Elfogadva 8ms 4764 KiB
10 Elfogadva 7ms 4716 KiB
subtask3 10/10
11 Elfogadva 24ms 4776 KiB
12 Elfogadva 24ms 4788 KiB
13 Elfogadva 25ms 4972 KiB
14 Elfogadva 24ms 5184 KiB
15 Elfogadva 23ms 5284 KiB
16 Elfogadva 25ms 5472 KiB
17 Elfogadva 28ms 7076 KiB
subtask4 15/15
18 Elfogadva 4ms 5436 KiB
19 Elfogadva 3ms 5428 KiB
20 Elfogadva 16ms 7120 KiB
21 Elfogadva 4ms 5640 KiB
22 Elfogadva 17ms 7236 KiB
23 Elfogadva 3ms 5904 KiB
24 Elfogadva 3ms 5956 KiB
25 Elfogadva 3ms 5864 KiB
26 Elfogadva 3ms 5908 KiB
27 Elfogadva 13ms 6876 KiB
subtask5 55/55
28 Elfogadva 37ms 7440 KiB
29 Elfogadva 37ms 7572 KiB
30 Elfogadva 27ms 6064 KiB
31 Elfogadva 28ms 6024 KiB
32 Elfogadva 27ms 6340 KiB
33 Elfogadva 25ms 6024 KiB
34 Elfogadva 32ms 6124 KiB
35 Elfogadva 28ms 6012 KiB
36 Elfogadva 32ms 6348 KiB
37 Elfogadva 32ms 6472 KiB
38 Elfogadva 41ms 7104 KiB
39 Elfogadva 48ms 7576 KiB