Submission #25867

#	Time	Username	Problem	Language	Result	Execution time	Memory
25867		gs14004	Brunhilda’s Birthday (BOI13_brunhilda)	C++11	100 / 100	463 ms	80144 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

int n, q;
int nxt[10000005];
int dp[10000005];

int main(){
	scanf("%d %d",&n,&q);
	for(int i=1; i<=n; i++){
		int x;
		scanf("%d",&x);
		for(int j=x; j-1<=10000000; j+=x){
			nxt[j-1] = x-1;
		}
		nxt[10000000] = max(nxt[10000000], 10000000 % x);
	}
	for(int i=10000000; i; i--) nxt[i] = max(nxt[i], nxt[i+1] - 1);
	for(int i=1; i<=10000000; i++){
		if(dp[i - nxt[i]] == -1 || nxt[i] == 0) dp[i] = -1;
		else dp[i] = dp[i - nxt[i]] + 1;
	}
	while(q--){
		int x;
		scanf("%d",&x);
		if(dp[x] < 0) puts("oo");
		else printf("%d\n", dp[x]);
	}
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:12:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
                      ^
brunhilda.cpp:15:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
                 ^
brunhilda.cpp:28:17: 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