Submission #256326

#	Time	Username	Problem	Language	Result	Execution time	Memory
256326		Saboon	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	400 ms	80760 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
 
const int maxn = 1e7 + 10;

int r[maxn], dp[maxn];
bitset<maxn> mark;
 
int main(){
	ios_base::sync_with_stdio(false);
	int m, q;
	scanf("%d%d", &m, &q);
	int n = 10*1000*1000;
	while (m --){
		int x;
		scanf("%d", &x);
		if (mark[x])
			continue;
		mark[x] = 1;
		for (int i = 0; i <= n; i += x)
			r[i] = max(r[i], i+x);
	}
	for (int i = 1; i <= n; i++)
		r[i] = max(r[i], r[i-1]);
	int mxm = n+1;
	int last = 0;
	for (int i = 1; i <= n; i++){
		if (r[last] <= i)
			last = i-1;
		if (r[last] == i){
			mxm = i;
			break;
		}
		dp[i] = dp[last] + 1;
	}
	while (q --){
		int x;
		scanf("%d", &x);
		if (x >= mxm)
			printf("oo\n");
		else
			printf("%d\n", dp[x]);
	}
}

Compilation message (stderr)

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