Submission #152835

#	Time	Username	Problem	Language	Result	Execution time	Memory
152835		Vlatko	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	8.10 / 100	432 ms	41968 KiB

brunhilda

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

typedef long long ll;
typedef pair<int, int> pii;

const int inf = 1e9;
const int maxn = 1e7 + 5;

int m, q;
vector<int> primes;
int dp[maxn];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> m >> q;
    for (int i = 0; i < m; ++i) {
		int p;
		cin >> p;
		primes.push_back(p);
	}
	for (int x = 1; x < maxn; ++x) {
		int bestp = -1;
		for (int j = m-1; j >= max(0, m-10); --j) {
			if (x % primes[j] != 0) {
				bestp = primes[j];
				break;
			}
		}
		if (bestp == -1) {
			dp[x] = inf;
		} else {
			//if (x < 10)
			//cout << x << " -> " << x - (x%bestp) << endl;
			dp[x] = 1 + dp[x - (x % bestp)];
		}
	}
	while (q--) {
		int x;
		cin >> x;
		if (dp[x] < inf) cout << dp[x] << endl;
		else cout << "oo\n";
	}
}

• Subtask 1: 1.1111111111111112 / 20
• Subtask 2: 5.555555555555555 / 20
• Subtask 3: 1.4285714285714286 / 60