#include "bits/stdc++.h"
using namespace std;
//#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
using i128 = __int128;
const int N = 1e7 + 10, INF = 0x3f3f3f3f;
int steps[N], maxp[N];
void solve() {
int m, q;
priority_queue<ii, vector<ii>, greater<ii>> pq;
cin >> m >> q;
memset(steps, 0x3f, sizeof steps);
for(int i = 0; i < m; ++i) {
int p;
cin >> p;
for(int j = 0; j < N; j += p) maxp[j] = p;
}
pq.emplace(1, maxp[0]);
for(int i = 1; i < N; ++i) {
while(!pq.empty() && pq.top().sc <= i) pq.pop();
if(!pq.empty()) {
steps[i] = pq.top().fi;
if(maxp[i]) pq.emplace(steps[i] + 1, i + maxp[i]);
}
}
while(q--) {
int n;
cin >> n;
if(steps[n] == INF) {
cout << "oo\n";
continue;
}
cout << steps[n] << '\n';
}
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
78540 KB |
Output is correct |
| 2 |
Correct |
415 ms |
78588 KB |
Output is correct |
| 3 |
Correct |
53 ms |
78536 KB |
Output is correct |
| 4 |
Correct |
90 ms |
78636 KB |
Output is correct |
| 5 |
Correct |
169 ms |
78580 KB |
Output is correct |
| 6 |
Correct |
41 ms |
78540 KB |
Output is correct |
| 7 |
Correct |
53 ms |
78576 KB |
Output is correct |
| 8 |
Correct |
76 ms |
78540 KB |
Output is correct |
| 9 |
Correct |
371 ms |
78580 KB |
Output is correct |
| 10 |
Correct |
433 ms |
78588 KB |
Output is correct |
| 11 |
Correct |
385 ms |
78532 KB |
Output is correct |
| 12 |
Correct |
77 ms |
78576 KB |
Output is correct |
| 13 |
Correct |
785 ms |
78792 KB |
Output is correct |
| 14 |
Correct |
774 ms |
78828 KB |
Output is correct |
| 15 |
Correct |
398 ms |
78580 KB |
Output is correct |
| 16 |
Correct |
404 ms |
78592 KB |
Output is correct |
| 17 |
Correct |
200 ms |
78668 KB |
Output is correct |
| 18 |
Correct |
91 ms |
78668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
80792 KB |
Output is correct |
| 2 |
Correct |
419 ms |
95804 KB |
Output is correct |
| 3 |
Execution timed out |
1083 ms |
112040 KB |
Time limit exceeded |
| 4 |
Correct |
438 ms |
79244 KB |
Output is correct |
| 5 |
Execution timed out |
1086 ms |
95544 KB |
Time limit exceeded |
| 6 |
Correct |
559 ms |
79228 KB |
Output is correct |
| 7 |
Correct |
249 ms |
80840 KB |
Output is correct |
| 8 |
Correct |
342 ms |
78716 KB |
Output is correct |
| 9 |
Execution timed out |
1083 ms |
95572 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1088 ms |
112028 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1075 ms |
87140 KB |
Time limit exceeded |
| 12 |
Correct |
728 ms |
79312 KB |
Output is correct |
| 13 |
Correct |
280 ms |
79760 KB |
Output is correct |
| 14 |
Correct |
442 ms |
79312 KB |
Output is correct |
| 15 |
Execution timed out |
1087 ms |
87232 KB |
Time limit exceeded |
| 16 |
Correct |
442 ms |
95764 KB |
Output is correct |
| 17 |
Correct |
918 ms |
79240 KB |
Output is correct |
| 18 |
Execution timed out |
1075 ms |
145104 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
87316 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1076 ms |
87384 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1085 ms |
87320 KB |
Time limit exceeded |
| 4 |
Correct |
839 ms |
80256 KB |
Output is correct |
| 5 |
Correct |
469 ms |
96272 KB |
Output is correct |
| 6 |
Execution timed out |
1038 ms |
80796 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1083 ms |
95928 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1076 ms |
87492 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1048 ms |
87444 KB |
Time limit exceeded |
| 10 |
Correct |
834 ms |
79816 KB |
Output is correct |
| 11 |
Correct |
641 ms |
79472 KB |
Output is correct |
| 12 |
Correct |
979 ms |
79820 KB |
Output is correct |
| 13 |
Execution timed out |
1078 ms |
87188 KB |
Time limit exceeded |
| 14 |
Correct |
487 ms |
79776 KB |
Output is correct |
| 15 |
Correct |
997 ms |
79776 KB |
Output is correct |
| 16 |
Execution timed out |
1062 ms |
79948 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1083 ms |
87252 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1082 ms |
87340 KB |
Time limit exceeded |
| 19 |
Correct |
464 ms |
82884 KB |
Output is correct |
| 20 |
Execution timed out |
1088 ms |
87320 KB |
Time limit exceeded |
| 21 |
Correct |
592 ms |
80064 KB |
Output is correct |
| 22 |
Execution timed out |
1089 ms |
95948 KB |
Time limit exceeded |
| 23 |
Correct |
449 ms |
83144 KB |
Output is correct |
| 24 |
Correct |
217 ms |
79824 KB |
Output is correct |
| 25 |
Correct |
790 ms |
80060 KB |
Output is correct |
| 26 |
Correct |
812 ms |
80256 KB |
Output is correct |
| 27 |
Execution timed out |
1088 ms |
96024 KB |
Time limit exceeded |
| 28 |
Correct |
354 ms |
80464 KB |
Output is correct |
| 29 |
Execution timed out |
1098 ms |
96020 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1086 ms |
87488 KB |
Time limit exceeded |
| 31 |
Correct |
454 ms |
80528 KB |
Output is correct |
| 32 |
Correct |
514 ms |
80016 KB |
Output is correct |
| 33 |
Correct |
157 ms |
79716 KB |
Output is correct |
| 34 |
Execution timed out |
1103 ms |
95932 KB |
Time limit exceeded |
| 35 |
Correct |
403 ms |
80312 KB |
Output is correct |
| 36 |
Execution timed out |
1074 ms |
96012 KB |
Time limit exceeded |
| 37 |
Correct |
480 ms |
96164 KB |
Output is correct |
| 38 |
Execution timed out |
1029 ms |
80692 KB |
Time limit exceeded |
| 39 |
Correct |
292 ms |
80000 KB |
Output is correct |
| 40 |
Correct |
994 ms |
81112 KB |
Output is correct |
| 41 |
Execution timed out |
1084 ms |
145388 KB |
Time limit exceeded |
| 42 |
Correct |
972 ms |
80264 KB |
Output is correct |
