Submission #134091

#	Time	Username	Problem	Language	Result	Execution time	Memory
134091		wzy	Brunhilda’s Birthday (BOI13_brunhilda)	C++11	100 / 100	460 ms	118776 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
const int N = 100002;
#define pii pair<int,int> 
const int MX = 10000005;
int primes[N] ;
int m , q;
int dp[MX];
int adj[MX];
int vl[MX];
int dq[MX];
int currx = -1;
// valores formam sequencia (0 , 1 , 2, 3 ,...)
// pega o menor multiplo menor que i 
int32_t main(){
	scanf("%d%d" , &m , &q);
	for(int i = 0 ; i < MX ;i ++){
		dp[i] = 1000000000;
		adj[i] = -1;
		dq[i] = -1;
	}
	for(int i = 0 ; i < m ; i ++){
		scanf("%d" , &primes[i]);
		vl[++currx] = primes[i];
		adj[currx] = dq[0];
		dq[0] = currx;
	}
	dp[0] = 0;
	int curr = 0;	
	for(int i = 0 ; i < MX ; i ++){
		int w = dq[i];
		while(w != -1){
			int u = i + vl[w];
			curr = max(curr, i+1);
			curr = min(curr , MX - 1);
			// if(i < 8){
			// 	cout<<i<<" " <<w <<" " << u <<endl;
			// }
			for(int j = curr; j < min(u , MX) ; j++){
				dp[j] = dp[i] + 1;
			}
			curr = max(curr, u);
			curr = min(curr , MX - 1);
			int wx = adj[w];
			if(u < MX){
				adj[w] = dq[u];
				dq[u] = w;
			}
			w = wx;
		}
	}
	for(int i = 0 ; i < q; i ++){
		int x;
		scanf("%d" , &x);
		int u = dp[x];
		if(u >= 1000000000){
			printf("oo\n");
		}
		else{
			printf("%d\n" , u);
		}
	}
}

Compilation message (stderr)

brunhilda.cpp: In function 'int32_t main()':
brunhilda.cpp:16: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" , &primes[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~
brunhilda.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &x);
   ~~~~~^~~~~~~~~~~

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