Submission #230230

#	Time	Username	Problem	Language	Result	Execution time	Memory
230230		kshitij_sodani	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	76.35 / 100	296 ms	79352 KiB

brunhilda

#include <iostream>	
#include <bits/stdc++.h>	
using namespace std;	
typedef int64_t llo;	
#define mp make_pair	
#define pb push_back	
#define a first	
#define b second
#define endl '\n'	
int ma[10000001];

int dp[10000001];
//vector<int> fac[10000001];
int main(){	
	memset(ma,0,sizeof(ma));
	ios_base::sync_with_stdio(false);	
	cin.tie(NULL);
	int n,s;
	cin>>n>>s;
	int aa;
	int it[n];
	for(int i=0;i<n;i++){
		cin>>it[i];
	}
//	sort(it,it+n);
	for(int i=0;i<n;i++){
		for(int j=it[i];j<10000001;j+=it[i]){
			ma[j-1]=it[i]-1;
		}
	}
	for(int i=10000000-1;i>=0;i--){
		ma[i]=max(ma[i],ma[i+1]-1);
	}
	dp[0]=0;
	for(int j=1;j<10000001;j++){
		if(ma[j]==0){
			dp[j]=-1;
		}
		else if(dp[j-ma[j]]!=-1){
			dp[j]=dp[j-ma[j]]+1;
		}
		else{
			dp[j]=-1;
		}
	}


	while(s--){
		cin>>aa;
		if(dp[aa]==-1){
			cout<<"oo"<<endl;
		}
		else{
			cout<<dp[aa]<<endl;
		}
	}




	

	return 0;	
}

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