Submission #134510

#	Time	Username	Problem	Language	Result	Execution time	Memory
134510		degelo	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	2.22 / 100	1093 ms	1144 KiB

brunhilda

#include<bits/stdc++.h>
#define inf 1000000000
#define maxn 20000
using namespace std;
long long int prod=1;
int m,q;
int p[maxn];
int dp[maxn];
int DP(int k){
	if(dp[k]!=0) return dp[k];
	if(k==0) return 0;
	if(k<p[m-1]) return 1;
	int resp=inf;
	for(int i=0;i<m;i++){
		if(k%p[i]==0) continue;
		resp=min(resp,DP((k/p[i])*p[i])+1);
	}
	return resp;
}
int main(){
	scanf("%d %d",&m,&q); 
	for(int i=0;i<m;i++){
		scanf("%d",&p[i]);
	}
	for(int i=0;i<m;i++){
		prod*=p[i];
		if(prod>maxn) break;
	}
	for(int i=0;i<q;i++){
		int n;
		scanf("%d",&n);
		if(n>=prod) printf("oo\n");
		else printf("%d\n",DP(n));
	}
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&m,&q); 
  ~~~~~^~~~~~~~~~~~~~~
brunhilda.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p[i]);
   ~~~~~^~~~~~~~~~~~
brunhilda.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~

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