Submission #121592

#	Time	Username	Problem	Language	Result	Execution time	Memory
121592		Adhyyan1252	Brunhilda’s Birthday (BOI13_brunhilda)	C++11	100 / 100	441 ms	80252 KiB

brunhilda

#include<bits/stdc++.h>

using namespace std;

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int m, q; cin>>m>>q;
	vector<int> p(m);
	for(int i = 0; i < m; i++){
		cin>>p[i];
	}
	int mx = 1e7+3;
	vector<int> dp(mx, 0);
	for(int i: p){
		for(int j = i-1; j < mx; j += i){
			dp[j] = i-1;
		}
	}
	//cout<<"DONE"<<endl;
	int bestMod = 0;
	for(int i: p) {
		bestMod = max(bestMod, (mx-1)%i);
	}
	for(int i = mx-1; i >= 2; i--){
		bestMod = max(bestMod, dp[i]);
		assert(bestMod >= 0);
		dp[i] = bestMod;
		bestMod--;
	}
	//cout<<"DONE"<<endl;
	vector<int> ans(mx, 2*mx);
	//cout<<"DONE"<<endl;
	ans[0] = 0;
	for(int i = 1; i < p.back(); i++){
		ans[i] = 1;
	}
	//cout<<"DONE"<<endl;
	for(int i = p.back(); i < mx; i++){
		assert(i >= dp[i]);
		ans[i] = ans[i-dp[i]]+1;
	}
	for(int i = 0; i < q; i++){
		int v; cin>>v;
		if(ans[v] > mx){
			cout<<"oo\n";
		}else{
			cout<<ans[v]<<"\n";
		}
	}
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60