Submission #199451

#	Time	Username	Problem	Language	Result	Execution time	Memory
199451		TadijaSebez	Brunhilda’s Birthday (BOI13_brunhilda)	C++11	100 / 100	555 ms	120692 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
const int N=10000050;
const int Q=100050;
int dp[N],fir[N],go[Q],p[Q],n[Q],cnt[N],ptr;
void Add(int x,int i){go[i]=fir[x];fir[x]=i;}
int main(){
	int m,q;
	scanf("%i %i",&m,&q);
	for(int i=1;i<=m;i++)scanf("%i",&p[i]),Add(p[i],i),cnt[0]++;
	for(int i=1;i<N;i++){
		for(int id=fir[i],nxt;id;id=nxt){
			cnt[i-p[id]]--;
			cnt[i]++;
			nxt=go[id];
			if(i+p[id]<N)Add(i+p[id],id);
		}
		while(cnt[ptr]==0)ptr++;
		if(ptr==i){
			for(;i<N;i++)dp[i]=1e9;
			break;
		}
		dp[i]=dp[ptr]+1;
	}
	for(int i=1;i<=q;i++){
		scanf("%i",&n[i]);
		if(dp[n[i]]==1e9)printf("oo\n");
		else printf("%i\n",dp[n[i]]);
	}
	return 0;
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&m,&q);
  ~~~~~^~~~~~~~~~~~~~~
brunhilda.cpp:10:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++)scanf("%i",&p[i]),Add(p[i],i),cnt[0]++;
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
brunhilda.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&n[i]);
   ~~~~~^~~~~~~~~~~~

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