#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define el '\n'
#define ld long double
const int maxn=1e5+1,nn=1e7+1;
void amax(int &x,int y){if(y>x)x=y;}
int a[maxn],f[nn],ut[nn];
int m,n,q,oo=1e9,p;
bool ok;
int take(int z){
if(f[z]>=0) return f[z];
if(ut[z]==0){
f[z]=oo;
} else {
f[z]=min(oo,take(z-ut[z])+1);
}
return f[z];
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> m >> q;
for(int i=0;i<m;++i) cin >> a[i];
sort(a+0,a+m);
for(int i=0;i<m;++i)
for(int j=a[i]-1;j<nn;j+=a[i]) ut[j]=a[i]-1;
for(int i=nn-2;i>0;--i) amax(ut[i],ut[i+1]-1);
memset(f,-1,sizeof f);
f[0]=0;
while(q--){
cin >> n;
p=take(n);
if(p==oo){
cout << "oo" << el;
} else {
cout << p << el;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
78492 KB |
Output is correct |
| 2 |
Correct |
79 ms |
78480 KB |
Output is correct |
| 3 |
Correct |
72 ms |
78476 KB |
Output is correct |
| 4 |
Correct |
63 ms |
78576 KB |
Output is correct |
| 5 |
Correct |
74 ms |
78476 KB |
Output is correct |
| 6 |
Correct |
67 ms |
78476 KB |
Output is correct |
| 7 |
Correct |
73 ms |
78532 KB |
Output is correct |
| 8 |
Correct |
77 ms |
78532 KB |
Output is correct |
| 9 |
Correct |
90 ms |
78472 KB |
Output is correct |
| 10 |
Correct |
101 ms |
78480 KB |
Output is correct |
| 11 |
Correct |
105 ms |
78608 KB |
Output is correct |
| 12 |
Correct |
61 ms |
78532 KB |
Output is correct |
| 13 |
Correct |
166 ms |
78500 KB |
Output is correct |
| 14 |
Correct |
154 ms |
78500 KB |
Output is correct |
| 15 |
Correct |
83 ms |
78532 KB |
Output is correct |
| 16 |
Correct |
76 ms |
78488 KB |
Output is correct |
| 17 |
Correct |
81 ms |
78532 KB |
Output is correct |
| 18 |
Correct |
68 ms |
78476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
78524 KB |
Output is correct |
| 2 |
Correct |
88 ms |
78836 KB |
Output is correct |
| 3 |
Correct |
192 ms |
78768 KB |
Output is correct |
| 4 |
Correct |
84 ms |
78492 KB |
Output is correct |
| 5 |
Correct |
133 ms |
78676 KB |
Output is correct |
| 6 |
Correct |
81 ms |
78532 KB |
Output is correct |
| 7 |
Correct |
72 ms |
78524 KB |
Output is correct |
| 8 |
Correct |
90 ms |
78480 KB |
Output is correct |
| 9 |
Correct |
162 ms |
78760 KB |
Output is correct |
| 10 |
Correct |
187 ms |
78752 KB |
Output is correct |
| 11 |
Incorrect |
180 ms |
78640 KB |
Output isn't correct |
| 12 |
Correct |
110 ms |
78588 KB |
Output is correct |
| 13 |
Correct |
68 ms |
78504 KB |
Output is correct |
| 14 |
Correct |
91 ms |
78492 KB |
Output is correct |
| 15 |
Correct |
162 ms |
78660 KB |
Output is correct |
| 16 |
Correct |
87 ms |
78836 KB |
Output is correct |
| 17 |
Correct |
157 ms |
78492 KB |
Output is correct |
| 18 |
Correct |
153 ms |
78864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
171 ms |
78788 KB |
Output is correct |
| 2 |
Correct |
209 ms |
78760 KB |
Output is correct |
| 3 |
Correct |
223 ms |
78936 KB |
Output is correct |
| 4 |
Incorrect |
147 ms |
79068 KB |
Output isn't correct |
| 5 |
Incorrect |
117 ms |
79380 KB |
Output isn't correct |
| 6 |
Correct |
180 ms |
79024 KB |
Output is correct |
| 7 |
Correct |
147 ms |
79172 KB |
Output is correct |
| 8 |
Correct |
169 ms |
78840 KB |
Output is correct |
| 9 |
Correct |
200 ms |
78784 KB |
Output is correct |
| 10 |
Correct |
128 ms |
78628 KB |
Output is correct |
| 11 |
Incorrect |
120 ms |
78752 KB |
Output isn't correct |
| 12 |
Correct |
154 ms |
78644 KB |
Output is correct |
| 13 |
Correct |
189 ms |
79172 KB |
Output is correct |
| 14 |
Correct |
128 ms |
81044 KB |
Output is correct |
| 15 |
Incorrect |
170 ms |
78788 KB |
Output isn't correct |
| 16 |
Correct |
177 ms |
78632 KB |
Output is correct |
| 17 |
Correct |
160 ms |
78652 KB |
Output is correct |
| 18 |
Correct |
202 ms |
78808 KB |
Output is correct |
| 19 |
Incorrect |
83 ms |
78664 KB |
Output isn't correct |
| 20 |
Correct |
202 ms |
78928 KB |
Output is correct |
| 21 |
Incorrect |
138 ms |
79888 KB |
Output isn't correct |
| 22 |
Correct |
232 ms |
79544 KB |
Output is correct |
| 23 |
Correct |
122 ms |
79240 KB |
Output is correct |
| 24 |
Correct |
97 ms |
79264 KB |
Output is correct |
| 25 |
Incorrect |
158 ms |
79260 KB |
Output isn't correct |
| 26 |
Incorrect |
146 ms |
79128 KB |
Output isn't correct |
| 27 |
Correct |
219 ms |
79248 KB |
Output is correct |
| 28 |
Incorrect |
89 ms |
79252 KB |
Output isn't correct |
| 29 |
Correct |
223 ms |
79552 KB |
Output is correct |
| 30 |
Correct |
202 ms |
79296 KB |
Output is correct |
| 31 |
Correct |
109 ms |
79044 KB |
Output is correct |
| 32 |
Incorrect |
124 ms |
79260 KB |
Output isn't correct |
| 33 |
Incorrect |
93 ms |
79248 KB |
Output isn't correct |
| 34 |
Correct |
155 ms |
79044 KB |
Output is correct |
| 35 |
Incorrect |
96 ms |
79252 KB |
Output isn't correct |
| 36 |
Correct |
227 ms |
79276 KB |
Output is correct |
| 37 |
Incorrect |
132 ms |
79324 KB |
Output isn't correct |
| 38 |
Correct |
199 ms |
79164 KB |
Output is correct |
| 39 |
Incorrect |
119 ms |
79124 KB |
Output isn't correct |
| 40 |
Correct |
170 ms |
79076 KB |
Output is correct |
| 41 |
Correct |
150 ms |
79188 KB |
Output is correct |
| 42 |
Incorrect |
218 ms |
79264 KB |
Output isn't correct |
