Submission #26999

#	Time	Username	Problem	Language	Result	Execution time	Memory
26999		noobprogrammer	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	5.56 / 100	1000 ms	119596 KiB

brunhilda

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

int n , m , pr[100010] , mx[10000010] , ft[10000010] , ptr , dp[10000010] ;
const int N = 1e7 ; 
// 1e7 - x + 1 ;

void upd(int x , int val){
	for( ;x<=N ;x+= (x&(-x))) ft[x] = min(ft[x] , val) ;
}

int qr(int x){
	int res = 1e9 ; 
	for(;x>0;x-=(x&(-x)) ) res = min(ft[x] , res) ;
	return res ;
}

int main(){
	// freopen("in.txt" , "r" , stdin) ;
	// freopen("out.txt" , "w" , stdout) ;
	scanf("%d%d" , &n,&m ) ;
	for(int i = 1 ;i<=N;i++) ft[i] = 1e9 ; 
	for(int i=0;i<n;i++) {
		scanf("%d" , pr+i) ;
		for(int j=0 ; j <= (int)1e7 ; j+=pr[i]) mx[j] = max(mx[j] , pr[i]) ;
	}
	upd( 1e7 - mx[0] + 2 , 1 ) ;
	int val ;
	for(int i=1;i<=N;i++){
		ptr = N-i+1 ;
		dp[i] = qr(ptr) ;
		// printf("%d %d %d\n" , i , dp[i] , ptr) ;
		ptr = N - (i + mx[i] - 1 ) + 1 ; 
		if(dp[i] == 1e9) continue ;
		if(ptr > N) continue ;
		upd(ptr , dp[i] + 1) ;
	}
	for(int i=0;i<m;i++){
		scanf("%d" , &val) ;
		if(dp[val] == 1e9) printf("oo\n") ;
		else printf("%d\n" , dp[val] ) ;
	}
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:21:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" , &n,&m ) ;
                         ^
brunhilda.cpp:24:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , pr+i) ;
                      ^
brunhilda.cpp:39:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &val) ;
                      ^

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