#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+1e3;
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 |
66 ms |
78484 KB |
Output is correct |
| 2 |
Correct |
74 ms |
78532 KB |
Output is correct |
| 3 |
Correct |
69 ms |
78532 KB |
Output is correct |
| 4 |
Correct |
62 ms |
78532 KB |
Output is correct |
| 5 |
Correct |
72 ms |
78492 KB |
Output is correct |
| 6 |
Correct |
65 ms |
78592 KB |
Output is correct |
| 7 |
Correct |
66 ms |
78496 KB |
Output is correct |
| 8 |
Correct |
76 ms |
78484 KB |
Output is correct |
| 9 |
Correct |
89 ms |
78532 KB |
Output is correct |
| 10 |
Correct |
100 ms |
78532 KB |
Output is correct |
| 11 |
Correct |
91 ms |
78480 KB |
Output is correct |
| 12 |
Correct |
59 ms |
78484 KB |
Output is correct |
| 13 |
Correct |
158 ms |
78576 KB |
Output is correct |
| 14 |
Correct |
153 ms |
78612 KB |
Output is correct |
| 15 |
Correct |
82 ms |
78480 KB |
Output is correct |
| 16 |
Correct |
79 ms |
78524 KB |
Output is correct |
| 17 |
Correct |
76 ms |
78496 KB |
Output is correct |
| 18 |
Correct |
61 ms |
78484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
78548 KB |
Output is correct |
| 2 |
Correct |
83 ms |
78880 KB |
Output is correct |
| 3 |
Correct |
188 ms |
78756 KB |
Output is correct |
| 4 |
Correct |
85 ms |
78532 KB |
Output is correct |
| 5 |
Correct |
127 ms |
78680 KB |
Output is correct |
| 6 |
Correct |
75 ms |
78484 KB |
Output is correct |
| 7 |
Correct |
74 ms |
78532 KB |
Output is correct |
| 8 |
Correct |
81 ms |
78532 KB |
Output is correct |
| 9 |
Correct |
157 ms |
78744 KB |
Output is correct |
| 10 |
Correct |
185 ms |
78788 KB |
Output is correct |
| 11 |
Incorrect |
177 ms |
78644 KB |
Output isn't correct |
| 12 |
Correct |
110 ms |
78504 KB |
Output is correct |
| 13 |
Correct |
65 ms |
78552 KB |
Output is correct |
| 14 |
Correct |
82 ms |
78488 KB |
Output is correct |
| 15 |
Correct |
154 ms |
78648 KB |
Output is correct |
| 16 |
Correct |
81 ms |
78852 KB |
Output is correct |
| 17 |
Correct |
154 ms |
78492 KB |
Output is correct |
| 18 |
Correct |
156 ms |
78872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
78800 KB |
Output is correct |
| 2 |
Correct |
200 ms |
78788 KB |
Output is correct |
| 3 |
Correct |
198 ms |
78936 KB |
Output is correct |
| 4 |
Correct |
138 ms |
78788 KB |
Output is correct |
| 5 |
Correct |
114 ms |
79124 KB |
Output is correct |
| 6 |
Correct |
183 ms |
78880 KB |
Output is correct |
| 7 |
Correct |
159 ms |
78996 KB |
Output is correct |
| 8 |
Correct |
170 ms |
78816 KB |
Output is correct |
| 9 |
Correct |
174 ms |
78852 KB |
Output is correct |
| 10 |
Correct |
132 ms |
78636 KB |
Output is correct |
| 11 |
Correct |
114 ms |
78660 KB |
Output is correct |
| 12 |
Correct |
164 ms |
78660 KB |
Output is correct |
| 13 |
Correct |
201 ms |
78860 KB |
Output is correct |
| 14 |
Correct |
134 ms |
80708 KB |
Output is correct |
| 15 |
Correct |
158 ms |
78632 KB |
Output is correct |
| 16 |
Correct |
179 ms |
78636 KB |
Output is correct |
| 17 |
Correct |
176 ms |
78664 KB |
Output is correct |
| 18 |
Correct |
198 ms |
78820 KB |
Output is correct |
| 19 |
Correct |
74 ms |
78632 KB |
Output is correct |
| 20 |
Correct |
221 ms |
79000 KB |
Output is correct |
| 21 |
Correct |
144 ms |
79556 KB |
Output is correct |
| 22 |
Correct |
236 ms |
79128 KB |
Output is correct |
| 23 |
Correct |
116 ms |
78868 KB |
Output is correct |
| 24 |
Correct |
102 ms |
78868 KB |
Output is correct |
| 25 |
Correct |
156 ms |
78888 KB |
Output is correct |
| 26 |
Correct |
148 ms |
78844 KB |
Output is correct |
| 27 |
Correct |
254 ms |
79000 KB |
Output is correct |
| 28 |
Correct |
90 ms |
78872 KB |
Output is correct |
| 29 |
Correct |
244 ms |
79172 KB |
Output is correct |
| 30 |
Correct |
200 ms |
79052 KB |
Output is correct |
| 31 |
Correct |
114 ms |
78772 KB |
Output is correct |
| 32 |
Correct |
117 ms |
78876 KB |
Output is correct |
| 33 |
Correct |
89 ms |
78788 KB |
Output is correct |
| 34 |
Correct |
147 ms |
78968 KB |
Output is correct |
| 35 |
Correct |
93 ms |
79076 KB |
Output is correct |
| 36 |
Correct |
220 ms |
79100 KB |
Output is correct |
| 37 |
Correct |
108 ms |
79128 KB |
Output is correct |
| 38 |
Correct |
178 ms |
78772 KB |
Output is correct |
| 39 |
Correct |
105 ms |
78916 KB |
Output is correct |
| 40 |
Correct |
159 ms |
78784 KB |
Output is correct |
| 41 |
Correct |
127 ms |
79000 KB |
Output is correct |
| 42 |
Correct |
185 ms |
78876 KB |
Output is correct |
