#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
#define f first
#define s second
int A[100000];
int dp[10000001];
set<ii> transitions;
int main() {
int m, q; cin >> m >> q;
for (int i = 0; i < m; i++) cin >> A[i];
for (int i = 0; i < 10000001; i++) dp[i] = -1;
dp[0] = 0;
int nxtStart = 0, nxtVal = 0;
for (int i = 0; i < m; i++) {
nxtVal = max(nxtVal, A[i]);
transitions.insert({A[i],A[i]});
}
while (nxtStart != -1) {
int begin = nxtStart, end = begin + nxtVal;
nxtStart = -1;
nxtVal = 0;
end = min(end, 10000001);
while (!transitions.empty() && transitions.begin()->f < end) {
int x = transitions.begin()->s;
transitions.erase(transitions.begin());
int i = (end-1)/x*x;
if (nxtStart+nxtVal < i + x) {
nxtStart = i;
nxtVal = x;
}
int nxt = (end-1)/x*x+x;
if (nxt <= 10000000) transitions.insert({nxt,x});
}
for (int i = begin + 1; i < end; i++) {
if (dp[i] == -1) dp[i] = dp[begin]+1;
}
}
for (int i = 0; i < q; i++) {
int x; cin >> x;
if (dp[x] == -1) cout << "oo" << "\n";
else cout << dp[x] << "\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
26 ms |
39424 KB |
Output is correct |
| 2 |
Correct |
154 ms |
39500 KB |
Output is correct |
| 3 |
Correct |
29 ms |
39424 KB |
Output is correct |
| 4 |
Correct |
87 ms |
39416 KB |
Output is correct |
| 5 |
Correct |
195 ms |
39424 KB |
Output is correct |
| 6 |
Correct |
29 ms |
39424 KB |
Output is correct |
| 7 |
Correct |
28 ms |
39424 KB |
Output is correct |
| 8 |
Correct |
42 ms |
39424 KB |
Output is correct |
| 9 |
Correct |
320 ms |
39424 KB |
Output is correct |
| 10 |
Correct |
249 ms |
39532 KB |
Output is correct |
| 11 |
Correct |
249 ms |
39424 KB |
Output is correct |
| 12 |
Correct |
88 ms |
39544 KB |
Output is correct |
| 13 |
Correct |
240 ms |
39552 KB |
Output is correct |
| 14 |
Correct |
254 ms |
39672 KB |
Output is correct |
| 15 |
Correct |
134 ms |
39544 KB |
Output is correct |
| 16 |
Correct |
160 ms |
39416 KB |
Output is correct |
| 17 |
Correct |
201 ms |
39424 KB |
Output is correct |
| 18 |
Correct |
85 ms |
39424 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
67 ms |
40064 KB |
Output is correct |
| 2 |
Correct |
106 ms |
44024 KB |
Output is correct |
| 3 |
Correct |
187 ms |
43040 KB |
Output is correct |
| 4 |
Correct |
96 ms |
39660 KB |
Output is correct |
| 5 |
Correct |
144 ms |
42156 KB |
Output is correct |
| 6 |
Correct |
62 ms |
39672 KB |
Output is correct |
| 7 |
Correct |
63 ms |
40064 KB |
Output is correct |
| 8 |
Correct |
96 ms |
39552 KB |
Output is correct |
| 9 |
Correct |
197 ms |
43128 KB |
Output is correct |
| 10 |
Correct |
197 ms |
43000 KB |
Output is correct |
| 11 |
Correct |
222 ms |
41464 KB |
Output is correct |
| 12 |
Correct |
115 ms |
39552 KB |
Output is correct |
| 13 |
Correct |
45 ms |
39680 KB |
Output is correct |
| 14 |
Correct |
92 ms |
39552 KB |
Output is correct |
| 15 |
Correct |
169 ms |
41592 KB |
Output is correct |
| 16 |
Correct |
110 ms |
44028 KB |
Output is correct |
| 17 |
Correct |
209 ms |
39672 KB |
Output is correct |
| 18 |
Correct |
159 ms |
44608 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
273 ms |
42232 KB |
Output is correct |
| 2 |
Correct |
311 ms |
42204 KB |
Output is correct |
| 3 |
Correct |
372 ms |
42232 KB |
Output is correct |
| 4 |
Correct |
330 ms |
40056 KB |
Output is correct |
| 5 |
Correct |
384 ms |
44664 KB |
Output is correct |
| 6 |
Correct |
404 ms |
40212 KB |
Output is correct |
| 7 |
Correct |
333 ms |
44664 KB |
Output is correct |
| 8 |
Correct |
267 ms |
42104 KB |
Output is correct |
| 9 |
Correct |
266 ms |
42104 KB |
Output is correct |
| 10 |
Correct |
183 ms |
39800 KB |
Output is correct |
| 11 |
Correct |
179 ms |
39828 KB |
Output is correct |
| 12 |
Correct |
212 ms |
39928 KB |
Output is correct |
| 13 |
Correct |
450 ms |
41336 KB |
Output is correct |
| 14 |
Correct |
586 ms |
40060 KB |
Output is correct |
| 15 |
Correct |
238 ms |
39800 KB |
Output is correct |
| 16 |
Correct |
284 ms |
39928 KB |
Output is correct |
| 17 |
Correct |
215 ms |
41792 KB |
Output is correct |
| 18 |
Correct |
300 ms |
42360 KB |
Output is correct |
| 19 |
Correct |
105 ms |
39800 KB |
Output is correct |
| 20 |
Correct |
371 ms |
42232 KB |
Output is correct |
| 21 |
Correct |
471 ms |
40056 KB |
Output is correct |
| 22 |
Correct |
498 ms |
44792 KB |
Output is correct |
| 23 |
Correct |
356 ms |
41208 KB |
Output is correct |
| 24 |
Correct |
300 ms |
39928 KB |
Output is correct |
| 25 |
Correct |
389 ms |
39928 KB |
Output is correct |
| 26 |
Correct |
321 ms |
39928 KB |
Output is correct |
| 27 |
Correct |
401 ms |
44664 KB |
Output is correct |
| 28 |
Correct |
312 ms |
39800 KB |
Output is correct |
| 29 |
Correct |
527 ms |
44792 KB |
Output is correct |
| 30 |
Correct |
500 ms |
43408 KB |
Output is correct |
| 31 |
Correct |
289 ms |
39928 KB |
Output is correct |
| 32 |
Correct |
330 ms |
40184 KB |
Output is correct |
| 33 |
Correct |
278 ms |
39800 KB |
Output is correct |
| 34 |
Correct |
331 ms |
44720 KB |
Output is correct |
| 35 |
Correct |
314 ms |
39800 KB |
Output is correct |
| 36 |
Correct |
458 ms |
44280 KB |
Output is correct |
| 37 |
Correct |
387 ms |
44792 KB |
Output is correct |
| 38 |
Correct |
410 ms |
40184 KB |
Output is correct |
| 39 |
Correct |
323 ms |
39800 KB |
Output is correct |
| 40 |
Correct |
376 ms |
40184 KB |
Output is correct |
| 41 |
Correct |
264 ms |
44664 KB |
Output is correct |
| 42 |
Correct |
438 ms |
40116 KB |
Output is correct |
