#include <bits/stdc++.h>
using namespace std;
template <typename T> void Min(T &a, T b) {
a = min(a, b);
}
template <typename T> void Max(T &a, T b) {
a = max(a, b);
}
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e7 + 15;
int n, m, q, k, a[N];
int mx[N], dp[N];
main() {
memset(dp, 0x3f, sizeof(dp));
ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
cin >> m >> q;
while(m--) {
int p;
cin >> p;
for(int i = p - 1; i < N; i += p)
Max(mx[i], p - 1);
}
for(int i = N - 2; i; --i)
Max(mx[i], mx[i + 1] - 1);
dp[0] = 0;
for(int i = 1; i < N; ++i)
Min(dp[i], dp[i - mx[i]] + 1);
while(q--) {
int x;
cin >> x;
if(dp[x] == inf)
cout << "oo" << endl;
else
cout << dp[x] << endl;
}
return 0;
}
Compilation message
brunhilda.cpp:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
78584 KB |
Output is correct |
| 2 |
Correct |
130 ms |
78580 KB |
Output is correct |
| 3 |
Correct |
131 ms |
78584 KB |
Output is correct |
| 4 |
Correct |
140 ms |
78712 KB |
Output is correct |
| 5 |
Correct |
120 ms |
78584 KB |
Output is correct |
| 6 |
Correct |
111 ms |
78584 KB |
Output is correct |
| 7 |
Correct |
117 ms |
78584 KB |
Output is correct |
| 8 |
Correct |
125 ms |
78584 KB |
Output is correct |
| 9 |
Correct |
139 ms |
78584 KB |
Output is correct |
| 10 |
Correct |
156 ms |
78612 KB |
Output is correct |
| 11 |
Correct |
148 ms |
78584 KB |
Output is correct |
| 12 |
Correct |
113 ms |
78708 KB |
Output is correct |
| 13 |
Correct |
239 ms |
78680 KB |
Output is correct |
| 14 |
Correct |
274 ms |
78840 KB |
Output is correct |
| 15 |
Correct |
141 ms |
78716 KB |
Output is correct |
| 16 |
Correct |
137 ms |
78584 KB |
Output is correct |
| 17 |
Correct |
148 ms |
78692 KB |
Output is correct |
| 18 |
Correct |
148 ms |
78712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
78712 KB |
Output is correct |
| 2 |
Correct |
158 ms |
79352 KB |
Output is correct |
| 3 |
Correct |
311 ms |
79196 KB |
Output is correct |
| 4 |
Correct |
150 ms |
78804 KB |
Output is correct |
| 5 |
Correct |
223 ms |
78968 KB |
Output is correct |
| 6 |
Correct |
130 ms |
78588 KB |
Output is correct |
| 7 |
Correct |
126 ms |
78840 KB |
Output is correct |
| 8 |
Correct |
153 ms |
78736 KB |
Output is correct |
| 9 |
Correct |
259 ms |
79068 KB |
Output is correct |
| 10 |
Correct |
316 ms |
79228 KB |
Output is correct |
| 11 |
Incorrect |
309 ms |
78968 KB |
Output isn't correct |
| 12 |
Correct |
202 ms |
78792 KB |
Output is correct |
| 13 |
Correct |
118 ms |
78584 KB |
Output is correct |
| 14 |
Correct |
166 ms |
78756 KB |
Output is correct |
| 15 |
Correct |
253 ms |
78968 KB |
Output is correct |
| 16 |
Correct |
149 ms |
79352 KB |
Output is correct |
| 17 |
Correct |
253 ms |
78840 KB |
Output is correct |
| 18 |
Correct |
259 ms |
79484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
350 ms |
79352 KB |
Output is correct |
| 2 |
Correct |
350 ms |
79224 KB |
Output is correct |
| 3 |
Correct |
410 ms |
79608 KB |
Output is correct |
| 4 |
Incorrect |
361 ms |
79736 KB |
Output isn't correct |
| 5 |
Incorrect |
366 ms |
80376 KB |
Output isn't correct |
| 6 |
Correct |
477 ms |
79608 KB |
Output is correct |
| 7 |
Correct |
355 ms |
79864 KB |
Output is correct |
| 8 |
Correct |
317 ms |
79352 KB |
Output is correct |
| 9 |
Correct |
324 ms |
79352 KB |
Output is correct |
| 10 |
Correct |
257 ms |
78840 KB |
Output is correct |
| 11 |
Incorrect |
247 ms |
78840 KB |
Output isn't correct |
| 12 |
Correct |
327 ms |
78968 KB |
Output is correct |
| 13 |
Correct |
505 ms |
79864 KB |
Output is correct |
| 14 |
Correct |
366 ms |
79992 KB |
Output is correct |
| 15 |
Incorrect |
282 ms |
78968 KB |
Output isn't correct |
| 16 |
Correct |
297 ms |
78968 KB |
Output is correct |
| 17 |
Correct |
275 ms |
79124 KB |
Output is correct |
| 18 |
Correct |
343 ms |
79224 KB |
Output is correct |
| 19 |
Incorrect |
166 ms |
78840 KB |
Output isn't correct |
| 20 |
Correct |
393 ms |
79608 KB |
Output is correct |
| 21 |
Incorrect |
387 ms |
79992 KB |
Output isn't correct |
| 22 |
Correct |
514 ms |
80408 KB |
Output is correct |
| 23 |
Correct |
372 ms |
79864 KB |
Output is correct |
| 24 |
Correct |
360 ms |
79608 KB |
Output is correct |
| 25 |
Correct |
422 ms |
79712 KB |
Output is correct |
| 26 |
Incorrect |
377 ms |
79612 KB |
Output isn't correct |
| 27 |
Correct |
541 ms |
79824 KB |
Output is correct |
| 28 |
Incorrect |
473 ms |
79740 KB |
Output isn't correct |
| 29 |
Correct |
621 ms |
80248 KB |
Output is correct |
| 30 |
Correct |
540 ms |
80248 KB |
Output is correct |
| 31 |
Correct |
327 ms |
79740 KB |
Output is correct |
| 32 |
Incorrect |
360 ms |
79688 KB |
Output isn't correct |
| 33 |
Incorrect |
302 ms |
79608 KB |
Output isn't correct |
| 34 |
Correct |
335 ms |
79952 KB |
Output is correct |
| 35 |
Incorrect |
331 ms |
79736 KB |
Output isn't correct |
| 36 |
Correct |
555 ms |
80376 KB |
Output is correct |
| 37 |
Incorrect |
376 ms |
80504 KB |
Output isn't correct |
| 38 |
Correct |
441 ms |
79736 KB |
Output is correct |
| 39 |
Incorrect |
349 ms |
79864 KB |
Output isn't correct |
| 40 |
Correct |
423 ms |
79736 KB |
Output is correct |
| 41 |
Correct |
333 ms |
79992 KB |
Output is correct |
| 42 |
Correct |
490 ms |
80124 KB |
Output is correct |
