#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],n,m,q,p,oo,ans,k,f[nn],ut[nn];
int t;
bool ok;
void check(){
t=1;
ok=0;
for(int i=0;i<m;++i){
k=t*a[i];
if(t*a[i]<t || t*a[i]>oo || k/a[i]!=t){
ok=1;
return;
}
t=t*a[i];
}
}
int sol(int z){
if(f[z]>=0) return f[z];
f[z]=sol(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;
oo=1e7;
check();
while(q--){
cin >> n;
if(ok){
cout << sol(n);
} else {
if(n>=t){
cout << "oo";
} else {
cout << sol(n);
}
}
cout << el;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
78484 KB |
Output is correct |
| 2 |
Correct |
86 ms |
78480 KB |
Output is correct |
| 3 |
Correct |
71 ms |
78484 KB |
Output is correct |
| 4 |
Correct |
68 ms |
78476 KB |
Output is correct |
| 5 |
Correct |
72 ms |
78532 KB |
Output is correct |
| 6 |
Correct |
66 ms |
78476 KB |
Output is correct |
| 7 |
Correct |
68 ms |
78484 KB |
Output is correct |
| 8 |
Correct |
82 ms |
78536 KB |
Output is correct |
| 9 |
Correct |
96 ms |
78480 KB |
Output is correct |
| 10 |
Correct |
102 ms |
78480 KB |
Output is correct |
| 11 |
Correct |
98 ms |
78496 KB |
Output is correct |
| 12 |
Correct |
67 ms |
78476 KB |
Output is correct |
| 13 |
Correct |
174 ms |
78484 KB |
Output is correct |
| 14 |
Correct |
182 ms |
78484 KB |
Output is correct |
| 15 |
Correct |
81 ms |
78532 KB |
Output is correct |
| 16 |
Correct |
77 ms |
78540 KB |
Output is correct |
| 17 |
Correct |
82 ms |
78492 KB |
Output is correct |
| 18 |
Correct |
75 ms |
78616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
78576 KB |
Output is correct |
| 2 |
Correct |
80 ms |
78836 KB |
Output is correct |
| 3 |
Correct |
217 ms |
78748 KB |
Output is correct |
| 4 |
Correct |
85 ms |
78504 KB |
Output is correct |
| 5 |
Correct |
137 ms |
78676 KB |
Output is correct |
| 6 |
Correct |
77 ms |
78544 KB |
Output is correct |
| 7 |
Correct |
82 ms |
78536 KB |
Output is correct |
| 8 |
Correct |
98 ms |
78552 KB |
Output is correct |
| 9 |
Correct |
153 ms |
78764 KB |
Output is correct |
| 10 |
Correct |
207 ms |
78788 KB |
Output is correct |
| 11 |
Incorrect |
186 ms |
78660 KB |
Output isn't correct |
| 12 |
Correct |
118 ms |
78492 KB |
Output is correct |
| 13 |
Correct |
71 ms |
78500 KB |
Output is correct |
| 14 |
Correct |
87 ms |
78576 KB |
Output is correct |
| 15 |
Correct |
155 ms |
78772 KB |
Output is correct |
| 16 |
Correct |
111 ms |
78832 KB |
Output is correct |
| 17 |
Correct |
163 ms |
78488 KB |
Output is correct |
| 18 |
Correct |
158 ms |
78864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
191 ms |
78852 KB |
Output is correct |
| 2 |
Correct |
211 ms |
78812 KB |
Output is correct |
| 3 |
Correct |
208 ms |
78932 KB |
Output is correct |
| 4 |
Incorrect |
154 ms |
78744 KB |
Output isn't correct |
| 5 |
Runtime error |
202 ms |
262148 KB |
Execution killed with signal 9 |
| 6 |
Correct |
186 ms |
78764 KB |
Output is correct |
| 7 |
Correct |
147 ms |
78976 KB |
Output is correct |
| 8 |
Correct |
173 ms |
78820 KB |
Output is correct |
| 9 |
Correct |
173 ms |
78788 KB |
Output is correct |
| 10 |
Correct |
128 ms |
78632 KB |
Output is correct |
| 11 |
Incorrect |
139 ms |
78624 KB |
Output isn't correct |
| 12 |
Correct |
159 ms |
78628 KB |
Output is correct |
| 13 |
Correct |
184 ms |
78928 KB |
Output is correct |
| 14 |
Correct |
132 ms |
79888 KB |
Output is correct |
| 15 |
Incorrect |
164 ms |
78732 KB |
Output isn't correct |
| 16 |
Correct |
182 ms |
78648 KB |
Output is correct |
| 17 |
Correct |
158 ms |
78784 KB |
Output is correct |
| 18 |
Correct |
233 ms |
78816 KB |
Output is correct |
| 19 |
Incorrect |
76 ms |
78624 KB |
Output isn't correct |
| 20 |
Correct |
191 ms |
79052 KB |
Output is correct |
| 21 |
Incorrect |
139 ms |
79300 KB |
Output isn't correct |
| 22 |
Correct |
221 ms |
79056 KB |
Output is correct |
| 23 |
Correct |
118 ms |
78884 KB |
Output is correct |
| 24 |
Correct |
97 ms |
78892 KB |
Output is correct |
| 25 |
Incorrect |
155 ms |
78876 KB |
Output isn't correct |
| 26 |
Incorrect |
138 ms |
78788 KB |
Output isn't correct |
| 27 |
Correct |
215 ms |
79116 KB |
Output is correct |
| 28 |
Runtime error |
200 ms |
262148 KB |
Execution killed with signal 9 |
| 29 |
Correct |
208 ms |
79052 KB |
Output is correct |
| 30 |
Correct |
204 ms |
79008 KB |
Output is correct |
| 31 |
Correct |
107 ms |
78764 KB |
Output is correct |
| 32 |
Incorrect |
119 ms |
78788 KB |
Output isn't correct |
| 33 |
Incorrect |
91 ms |
78752 KB |
Output isn't correct |
| 34 |
Correct |
153 ms |
79020 KB |
Output is correct |
| 35 |
Runtime error |
197 ms |
262148 KB |
Execution killed with signal 9 |
| 36 |
Correct |
237 ms |
79092 KB |
Output is correct |
| 37 |
Runtime error |
208 ms |
262148 KB |
Execution killed with signal 9 |
| 38 |
Correct |
190 ms |
78772 KB |
Output is correct |
| 39 |
Incorrect |
105 ms |
78788 KB |
Output isn't correct |
| 40 |
Correct |
161 ms |
78776 KB |
Output is correct |
| 41 |
Correct |
135 ms |
78976 KB |
Output is correct |
| 42 |
Incorrect |
187 ms |
78888 KB |
Output isn't correct |
