Submission #1216229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216229		A_M_Namdar	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	0 / 100	839 ms	327680 KiB

brunhilda

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

const int N = 1e5 + 10, M = 1e7 + 10;
int m, q, p[N], dp[M];
vector<int> vec[M];

void input() {
	cin >> m >> q;
	for (int i = 0; i < m; i++) 
		cin >> p[i];
}

void solve() {
	for (int i = 0; i < m; i++) 
		for (int j = p[i]; j < M; j += p[i]) 
			vec[j].push_back(p[i]);
	set<pair<int, int>> s;
	for (int i = 0; i < m; i++) 
		s.insert({0, p[i]});
	for (int i = 1; i < M; i++) {
		for (int x: vec[i]) {
			s.erase({i - x, x});
			s.insert({i, x});
		}
		dp[i] = 1e9 + 10;
		dp[i] = min(dp[i], dp[i - (i % (s.begin())->second)] + 1);
	}
	while (q--) {
		int n;
		cin >> n;
		if (dp[n] > 1e9) cout << "oo\n";
		else cout << dp[n] << '\n';
	}
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	solve();
}

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