Submission #631360

#	Time	Username	Problem	Language	Result	Execution time	Memory
631360		uylulu	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	24.76 / 100	379 ms	159920 KiB

brunhilda

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define endl "\n"

const int N = 1e7,len = 1e5;

int mx[N + 1],dp[N + 1],num[N + 1];
int m,q,lim;

int lcm(int a,int b) {
	return a*b/(__gcd(a,b));
}

void init() {
	lim = num[1];
	for(int i = 2;i <= m;i++) {
		if(lim > N) break;
		lim = lcm(lim,num[i]);
	}
	for(int i = 1;i <= m;i++) {
		for(int j = 1;num[i]*j <= N;j++) {
			mx[num[i]*j] = max(num[i],mx[num[i]*j]);
		}
	}
	dp[0] = 0;
	for(int i = 1;i < num[m];i++) {
		dp[i] = 1;
	}
	int lst = 0,temp = 0;
	for(int i = 1;i < num[m];i++) {
		if(temp < (mx[i] - 1) - (num[m] - i)) {
			temp = (mx[i] - 1) - (num[m] - i);
			lst = i;
		}
	}
	for(int i = num[m];i <= lim;i++) {
		while(mx[lst] - 1 < (i - lst)) lst++;
		dp[i] = dp[lst] + 1;
	}
}

signed main() {
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);

	cin>>m>>q;
	for(int i = 1;i <= m;i++) cin>>num[i];
	init();
	while(q--) {
		int x;
		cin>>x;
		if(x >= lim) {
			cout<<"oo"<<endl;
		} else {
			cout<<dp[x]<<endl;
		}
	}
}

• Subtask 1: 8.88888888888889 / 20
• Subtask 2: 4.444444444444445 / 20
• Subtask 3: 11.428571428571429 / 60