#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+100;
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 |
74 ms |
78532 KB |
Output is correct |
| 2 |
Correct |
97 ms |
78484 KB |
Output is correct |
| 3 |
Correct |
75 ms |
78604 KB |
Output is correct |
| 4 |
Correct |
67 ms |
78480 KB |
Output is correct |
| 5 |
Correct |
81 ms |
78480 KB |
Output is correct |
| 6 |
Correct |
75 ms |
78496 KB |
Output is correct |
| 7 |
Correct |
78 ms |
78564 KB |
Output is correct |
| 8 |
Correct |
87 ms |
78488 KB |
Output is correct |
| 9 |
Correct |
97 ms |
78536 KB |
Output is correct |
| 10 |
Correct |
114 ms |
78496 KB |
Output is correct |
| 11 |
Correct |
102 ms |
78484 KB |
Output is correct |
| 12 |
Correct |
65 ms |
78476 KB |
Output is correct |
| 13 |
Correct |
172 ms |
78544 KB |
Output is correct |
| 14 |
Correct |
167 ms |
78492 KB |
Output is correct |
| 15 |
Correct |
95 ms |
78480 KB |
Output is correct |
| 16 |
Correct |
88 ms |
78476 KB |
Output is correct |
| 17 |
Correct |
82 ms |
78552 KB |
Output is correct |
| 18 |
Correct |
87 ms |
78496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
78536 KB |
Output is correct |
| 2 |
Correct |
91 ms |
78840 KB |
Output is correct |
| 3 |
Correct |
203 ms |
78764 KB |
Output is correct |
| 4 |
Correct |
99 ms |
78500 KB |
Output is correct |
| 5 |
Correct |
155 ms |
78700 KB |
Output is correct |
| 6 |
Correct |
81 ms |
78500 KB |
Output is correct |
| 7 |
Correct |
79 ms |
78528 KB |
Output is correct |
| 8 |
Correct |
89 ms |
78488 KB |
Output is correct |
| 9 |
Correct |
166 ms |
78848 KB |
Output is correct |
| 10 |
Correct |
195 ms |
78756 KB |
Output is correct |
| 11 |
Incorrect |
193 ms |
78660 KB |
Output isn't correct |
| 12 |
Correct |
125 ms |
78488 KB |
Output is correct |
| 13 |
Correct |
71 ms |
78496 KB |
Output is correct |
| 14 |
Correct |
90 ms |
78508 KB |
Output is correct |
| 15 |
Correct |
167 ms |
78644 KB |
Output is correct |
| 16 |
Correct |
89 ms |
78836 KB |
Output is correct |
| 17 |
Correct |
180 ms |
78496 KB |
Output is correct |
| 18 |
Correct |
168 ms |
78916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
78836 KB |
Output is correct |
| 2 |
Correct |
221 ms |
78816 KB |
Output is correct |
| 3 |
Correct |
207 ms |
79044 KB |
Output is correct |
| 4 |
Incorrect |
151 ms |
78848 KB |
Output isn't correct |
| 5 |
Incorrect |
123 ms |
79128 KB |
Output isn't correct |
| 6 |
Correct |
201 ms |
78900 KB |
Output is correct |
| 7 |
Correct |
163 ms |
79044 KB |
Output is correct |
| 8 |
Correct |
182 ms |
78808 KB |
Output is correct |
| 9 |
Correct |
184 ms |
78788 KB |
Output is correct |
| 10 |
Correct |
143 ms |
78648 KB |
Output is correct |
| 11 |
Correct |
123 ms |
78588 KB |
Output is correct |
| 12 |
Correct |
170 ms |
78656 KB |
Output is correct |
| 13 |
Correct |
204 ms |
78916 KB |
Output is correct |
| 14 |
Correct |
135 ms |
80676 KB |
Output is correct |
| 15 |
Correct |
173 ms |
78632 KB |
Output is correct |
| 16 |
Correct |
190 ms |
78636 KB |
Output is correct |
| 17 |
Correct |
186 ms |
78660 KB |
Output is correct |
| 18 |
Correct |
237 ms |
78820 KB |
Output is correct |
| 19 |
Incorrect |
85 ms |
78532 KB |
Output isn't correct |
| 20 |
Correct |
212 ms |
78916 KB |
Output is correct |
| 21 |
Incorrect |
146 ms |
79560 KB |
Output isn't correct |
| 22 |
Correct |
262 ms |
79128 KB |
Output is correct |
| 23 |
Correct |
120 ms |
78860 KB |
Output is correct |
| 24 |
Correct |
103 ms |
78868 KB |
Output is correct |
| 25 |
Correct |
171 ms |
78920 KB |
Output is correct |
| 26 |
Incorrect |
151 ms |
78836 KB |
Output isn't correct |
| 27 |
Correct |
234 ms |
79012 KB |
Output is correct |
| 28 |
Incorrect |
99 ms |
78884 KB |
Output isn't correct |
| 29 |
Correct |
241 ms |
79140 KB |
Output is correct |
| 30 |
Correct |
206 ms |
79044 KB |
Output is correct |
| 31 |
Correct |
141 ms |
78772 KB |
Output is correct |
| 32 |
Correct |
128 ms |
78748 KB |
Output is correct |
| 33 |
Correct |
99 ms |
78752 KB |
Output is correct |
| 34 |
Correct |
156 ms |
79004 KB |
Output is correct |
| 35 |
Incorrect |
96 ms |
78788 KB |
Output isn't correct |
| 36 |
Correct |
246 ms |
79172 KB |
Output is correct |
| 37 |
Incorrect |
117 ms |
79072 KB |
Output isn't correct |
| 38 |
Correct |
198 ms |
78756 KB |
Output is correct |
| 39 |
Correct |
113 ms |
78860 KB |
Output is correct |
| 40 |
Correct |
165 ms |
78784 KB |
Output is correct |
| 41 |
Correct |
137 ms |
79000 KB |
Output is correct |
| 42 |
Correct |
191 ms |
78896 KB |
Output is correct |
