#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
vector<int> a(n), d((int) 1e7 + 7), dp((int) 1e7 + 7, 1e9);
for (int &x : a) {
cin >> x;
for (int i = x - 1; i <= 1e7; i += x) {
d[i] = x - 1;
}
}
for (int i = 1e7; i > 0; i--) d[i] = max(d[i], d[i + 1] - 1);
dp[0] = 0;
for (int i = 1; i <= 1e7; i++) {
dp[i] = dp[i - d[i]] + 1;
}
while (q--) {
int x; cin >> x;
cout << (dp[x] >= 1e9 ? "oo" : to_string(dp[x])) << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
122 ms |
156872 KB |
Output is correct |
2 |
Correct |
155 ms |
156872 KB |
Output is correct |
3 |
Correct |
165 ms |
156832 KB |
Output is correct |
4 |
Correct |
117 ms |
156920 KB |
Output is correct |
5 |
Correct |
141 ms |
156848 KB |
Output is correct |
6 |
Correct |
127 ms |
156764 KB |
Output is correct |
7 |
Correct |
155 ms |
156740 KB |
Output is correct |
8 |
Correct |
174 ms |
156740 KB |
Output is correct |
9 |
Correct |
162 ms |
156816 KB |
Output is correct |
10 |
Correct |
195 ms |
156996 KB |
Output is correct |
11 |
Correct |
174 ms |
156820 KB |
Output is correct |
12 |
Correct |
115 ms |
156744 KB |
Output is correct |
13 |
Correct |
242 ms |
156784 KB |
Output is correct |
14 |
Correct |
244 ms |
156928 KB |
Output is correct |
15 |
Correct |
164 ms |
156864 KB |
Output is correct |
16 |
Correct |
167 ms |
156812 KB |
Output is correct |
17 |
Correct |
133 ms |
156912 KB |
Output is correct |
18 |
Correct |
125 ms |
156912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
131 ms |
156984 KB |
Output is correct |
2 |
Correct |
144 ms |
158276 KB |
Output is correct |
3 |
Correct |
295 ms |
157844 KB |
Output is correct |
4 |
Correct |
157 ms |
157004 KB |
Output is correct |
5 |
Correct |
216 ms |
157508 KB |
Output is correct |
6 |
Correct |
145 ms |
156856 KB |
Output is correct |
7 |
Correct |
128 ms |
156992 KB |
Output is correct |
8 |
Correct |
165 ms |
156888 KB |
Output is correct |
9 |
Correct |
235 ms |
157604 KB |
Output is correct |
10 |
Correct |
297 ms |
157512 KB |
Output is correct |
11 |
Incorrect |
279 ms |
157124 KB |
Output isn't correct |
12 |
Correct |
188 ms |
156876 KB |
Output is correct |
13 |
Correct |
170 ms |
156784 KB |
Output is correct |
14 |
Correct |
154 ms |
156872 KB |
Output is correct |
15 |
Correct |
251 ms |
157124 KB |
Output is correct |
16 |
Correct |
179 ms |
157580 KB |
Output is correct |
17 |
Correct |
264 ms |
157004 KB |
Output is correct |
18 |
Correct |
241 ms |
157732 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
267 ms |
157288 KB |
Output is correct |
2 |
Correct |
320 ms |
157276 KB |
Output is correct |
3 |
Correct |
305 ms |
157388 KB |
Output is correct |
4 |
Incorrect |
243 ms |
157132 KB |
Output isn't correct |
5 |
Incorrect |
190 ms |
157784 KB |
Output isn't correct |
6 |
Correct |
280 ms |
157184 KB |
Output is correct |
7 |
Correct |
245 ms |
157732 KB |
Output is correct |
8 |
Correct |
268 ms |
157276 KB |
Output is correct |
9 |
Correct |
271 ms |
157276 KB |
Output is correct |
10 |
Correct |
203 ms |
156912 KB |
Output is correct |
11 |
Incorrect |
216 ms |
156864 KB |
Output isn't correct |
12 |
Correct |
248 ms |
156940 KB |
Output is correct |
13 |
Correct |
275 ms |
157392 KB |
Output is correct |
14 |
Correct |
211 ms |
157476 KB |
Output is correct |
15 |
Incorrect |
265 ms |
156904 KB |
Output isn't correct |
16 |
Correct |
280 ms |
156996 KB |
Output is correct |
17 |
Correct |
254 ms |
157224 KB |
Output is correct |
18 |
Correct |
296 ms |
157364 KB |
Output is correct |
19 |
Incorrect |
164 ms |
156868 KB |
Output isn't correct |
20 |
Correct |
304 ms |
157484 KB |
Output is correct |
21 |
Incorrect |
221 ms |
157380 KB |
Output isn't correct |
22 |
Correct |
333 ms |
157784 KB |
Output is correct |
23 |
Correct |
168 ms |
157328 KB |
Output is correct |
24 |
Correct |
156 ms |
157112 KB |
Output is correct |
25 |
Incorrect |
241 ms |
157120 KB |
Output isn't correct |
26 |
Incorrect |
233 ms |
157140 KB |
Output isn't correct |
27 |
Correct |
332 ms |
157656 KB |
Output is correct |
28 |
Incorrect |
155 ms |
157124 KB |
Output isn't correct |
29 |
Correct |
287 ms |
157780 KB |
Output is correct |
30 |
Correct |
263 ms |
157540 KB |
Output is correct |
31 |
Correct |
170 ms |
157052 KB |
Output is correct |
32 |
Incorrect |
186 ms |
157124 KB |
Output isn't correct |
33 |
Incorrect |
149 ms |
157064 KB |
Output isn't correct |
34 |
Correct |
256 ms |
157652 KB |
Output is correct |
35 |
Incorrect |
154 ms |
157176 KB |
Output isn't correct |
36 |
Correct |
314 ms |
157716 KB |
Output is correct |
37 |
Incorrect |
186 ms |
157992 KB |
Output isn't correct |
38 |
Correct |
269 ms |
157188 KB |
Output is correct |
39 |
Incorrect |
167 ms |
157124 KB |
Output isn't correct |
40 |
Correct |
248 ms |
157256 KB |
Output is correct |
41 |
Correct |
216 ms |
157652 KB |
Output is correct |
42 |
Incorrect |
285 ms |
157248 KB |
Output isn't correct |