Submission #971679

#	Time	Username	Problem	Language	Result	Execution time	Memory
971679		NintsiChkhaidze	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	670 ms	158604 KiB

brunhilda

#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
using namespace std;
 
const int N = 1e6 + 5;
int a[100003],inf=1e9;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
 
	int n,q;
	cin>>n>>q;
 
	int m = 20000000;
	vector <int> prv(m + 1),dp(m + 1);
	for (int i = 1;i <= n; i++){
		cin >> a[i];
		for (int j = a[i] - 1; j <= m; j += a[i])
			prv[j] = max(prv[j],a[i] - 1);
	}
	
	for (int i=m;i>=1;i--){
		prv[i]=max(prv[i],prv[i + 1] - 1);
	}

	dp[0] = 0;
	for (int i = 1;i <= m; i++){
		dp[i] = inf;
		if (i >= prv[i]) 
			dp[i] = min(dp[i],dp[i - prv[i]] + 1);
	}
 	
	while (q--){
		int x;
		cin>>x;
		if (dp[x] == 1e9) cout<<"oo"<<endl;
		else cout<<dp[x]<<endl;
	}
}	

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