Submission #1216249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216249		A_M_Namdar	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	100 / 100	253 ms	44776 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 10, M = 1e7 + 10;
int m, q, p[N], dp[M];
set<pair<int, int>> s;
 
void input() {
	cin >> m >> q;
	for (int i = 0; i < m; i++) 
		cin >> p[i];
}
 
void solve() {
	for (int i = 0; i < m; i++) 
		s.insert({0, p[i]});
	for (int i = 1; i < M; i++) {
		dp[i] = 1e9 + 10;
		while (s.begin()->first != i - (i % s.begin()->second)) {
			int tmp = s.begin()->second;
			s.erase(s.begin());
			s.insert({i - (i % tmp), tmp});
		}
		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: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60