Submission #10,160

2024-03-28 19:50:39

Az óvodai lét elviselhetetlen könnyűsége #2

cpp17

Accepted 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;
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	3ms	3160 KiB
		2	Accepted	25ms	3508 KiB
subtask2	20/20
		3	Accepted	4ms	3728 KiB
		4	Accepted	4ms	3940 KiB
		5	Accepted	4ms	4140 KiB
		6	Accepted	16ms	4336 KiB
		7	Accepted	9ms	4568 KiB
		8	Accepted	7ms	4564 KiB
		9	Accepted	8ms	4764 KiB
		10	Accepted	7ms	4716 KiB
subtask3	10/10
		11	Accepted	24ms	4776 KiB
		12	Accepted	24ms	4788 KiB
		13	Accepted	25ms	4972 KiB
		14	Accepted	24ms	5184 KiB
		15	Accepted	23ms	5284 KiB
		16	Accepted	25ms	5472 KiB
		17	Accepted	28ms	7076 KiB
subtask4	15/15
		18	Accepted	4ms	5436 KiB
		19	Accepted	3ms	5428 KiB
		20	Accepted	16ms	7120 KiB
		21	Accepted	4ms	5640 KiB
		22	Accepted	17ms	7236 KiB
		23	Accepted	3ms	5904 KiB
		24	Accepted	3ms	5956 KiB
		25	Accepted	3ms	5864 KiB
		26	Accepted	3ms	5908 KiB
		27	Accepted	13ms	6876 KiB
subtask5	55/55
		28	Accepted	37ms	7440 KiB
		29	Accepted	37ms	7572 KiB
		30	Accepted	27ms	6064 KiB
		31	Accepted	28ms	6024 KiB
		32	Accepted	27ms	6340 KiB
		33	Accepted	25ms	6024 KiB
		34	Accepted	32ms	6124 KiB
		35	Accepted	28ms	6012 KiB
		36	Accepted	32ms	6348 KiB
		37	Accepted	32ms	6472 KiB
		38	Accepted	41ms	7104 KiB
		39	Accepted	48ms	7576 KiB