# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1265151 | lmquan | Brunhilda’s Birthday (BOI13_brunhilda) | C++20 | 303 ms | 98828 KiB |
#define taskname ""
#include <bits/stdc++.h>
using namespace std;
const long long kL = 1e7;
int main() {
if (fopen(taskname".inp", "r")) {
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m, q;
cin >> m >> q;
vector<int> p(m + 1);
long long s = 1;
for (int i = 1; i <= m; i++) {
cin >> p[i];
if (s <= kL) {
s *= p[i];
}
}
vector<int> f(kL + kL / 2 + 5, -1);
for (int i = 1; i <= m; i++) {
for (int j = p[i] - 1; j <= kL + kL / 2; j += p[i]) {
f[j] = p[i] - 1;
}
}
for (int i = kL + kL / 2 - 1; i >= 1; i--) {
f[i] = max(f[i], f[i + 1] - 1);
}
vector<int> dp(kL + 5, 0);
for (int i = 1; i <= kL; i++) {
dp[i] = dp[i - f[i]] + 1;
}
while (q--) {
int n;
cin >> n;
if (n >= s) {
cout << "oo";
} else {
cout << dp[n];
}
cout << '\n';
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |