#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
int ma[10000001];
int dp[10000001];
//vector<int> fac[10000001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,s;
cin>>n>>s;
int aa;
int it[n];
for(int i=0;i<n;i++){
cin>>it[i];
}
sort(it,it+n);
for(int i=0;i<n;i++){
for(int j=it[i];j<10000001;j+=it[i]){
ma[j-1]=it[i]-1;
}
}
for(int i=10000000-1;i>=0;i--){
ma[i]=max(ma[i],ma[i+1]-1);
}
dp[0]=0;
for(int j=1;j<10000001;j++){
if(ma[j]==0){
dp[j]=-1;
}
else if(dp[j-ma[j]]!=-1){
dp[j]=dp[j-ma[j]]+1;
}
else{
dp[j]=-1;
}
}
while(s--){
cin>>aa;
if(dp[aa]==-1){
cout<<"oo"<<endl;
}
else{
cout<<dp[aa]<<endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
78584 KB |
Output is correct |
| 2 |
Correct |
114 ms |
78584 KB |
Output is correct |
| 3 |
Correct |
112 ms |
78584 KB |
Output is correct |
| 4 |
Correct |
100 ms |
78712 KB |
Output is correct |
| 5 |
Correct |
113 ms |
78584 KB |
Output is correct |
| 6 |
Correct |
103 ms |
78584 KB |
Output is correct |
| 7 |
Correct |
108 ms |
78584 KB |
Output is correct |
| 8 |
Correct |
119 ms |
78584 KB |
Output is correct |
| 9 |
Correct |
132 ms |
78584 KB |
Output is correct |
| 10 |
Correct |
148 ms |
78584 KB |
Output is correct |
| 11 |
Correct |
133 ms |
78588 KB |
Output is correct |
| 12 |
Correct |
104 ms |
78712 KB |
Output is correct |
| 13 |
Correct |
215 ms |
78584 KB |
Output is correct |
| 14 |
Correct |
209 ms |
78712 KB |
Output is correct |
| 15 |
Correct |
126 ms |
78588 KB |
Output is correct |
| 16 |
Correct |
119 ms |
78584 KB |
Output is correct |
| 17 |
Correct |
114 ms |
78712 KB |
Output is correct |
| 18 |
Correct |
99 ms |
78712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
78712 KB |
Output is correct |
| 2 |
Correct |
131 ms |
79608 KB |
Output is correct |
| 3 |
Correct |
245 ms |
79304 KB |
Output is correct |
| 4 |
Correct |
132 ms |
78716 KB |
Output is correct |
| 5 |
Correct |
188 ms |
79116 KB |
Output is correct |
| 6 |
Correct |
114 ms |
78584 KB |
Output is correct |
| 7 |
Correct |
118 ms |
78712 KB |
Output is correct |
| 8 |
Correct |
125 ms |
78584 KB |
Output is correct |
| 9 |
Correct |
219 ms |
79352 KB |
Output is correct |
| 10 |
Correct |
260 ms |
79352 KB |
Output is correct |
| 11 |
Incorrect |
246 ms |
78968 KB |
Output isn't correct |
| 12 |
Correct |
162 ms |
78584 KB |
Output is correct |
| 13 |
Correct |
105 ms |
78672 KB |
Output is correct |
| 14 |
Correct |
126 ms |
78712 KB |
Output is correct |
| 15 |
Correct |
207 ms |
79096 KB |
Output is correct |
| 16 |
Correct |
137 ms |
79608 KB |
Output is correct |
| 17 |
Correct |
210 ms |
78712 KB |
Output is correct |
| 18 |
Incorrect |
210 ms |
79736 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
226 ms |
79740 KB |
Output is correct |
| 2 |
Correct |
255 ms |
79480 KB |
Output is correct |
| 3 |
Correct |
260 ms |
79864 KB |
Output is correct |
| 4 |
Incorrect |
182 ms |
79736 KB |
Output isn't correct |
| 5 |
Incorrect |
156 ms |
80760 KB |
Output isn't correct |
| 6 |
Correct |
230 ms |
79724 KB |
Output is correct |
| 7 |
Correct |
209 ms |
80504 KB |
Output is correct |
| 8 |
Correct |
217 ms |
79608 KB |
Output is correct |
| 9 |
Correct |
225 ms |
79608 KB |
Output is correct |
| 10 |
Correct |
181 ms |
78840 KB |
Output is correct |
| 11 |
Incorrect |
158 ms |
78840 KB |
Output isn't correct |
| 12 |
Correct |
203 ms |
78968 KB |
Output is correct |
| 13 |
Correct |
254 ms |
79992 KB |
Output is correct |
| 14 |
Correct |
167 ms |
80120 KB |
Output is correct |
| 15 |
Incorrect |
212 ms |
78968 KB |
Output isn't correct |
| 16 |
Correct |
227 ms |
78968 KB |
Output is correct |
| 17 |
Correct |
206 ms |
79224 KB |
Output is correct |
| 18 |
Correct |
253 ms |
79484 KB |
Output is correct |
| 19 |
Incorrect |
119 ms |
78840 KB |
Output isn't correct |
| 20 |
Correct |
251 ms |
79736 KB |
Output is correct |
| 21 |
Incorrect |
182 ms |
79992 KB |
Output isn't correct |
| 22 |
Correct |
281 ms |
80632 KB |
Output is correct |
| 23 |
Correct |
156 ms |
79992 KB |
Output is correct |
| 24 |
Correct |
134 ms |
79612 KB |
Output is correct |
| 25 |
Incorrect |
198 ms |
79708 KB |
Output isn't correct |
| 26 |
Incorrect |
185 ms |
79612 KB |
Output isn't correct |
| 27 |
Correct |
284 ms |
80248 KB |
Output is correct |
| 28 |
Incorrect |
131 ms |
79740 KB |
Output isn't correct |
| 29 |
Correct |
268 ms |
80724 KB |
Output is correct |
| 30 |
Correct |
247 ms |
80376 KB |
Output is correct |
| 31 |
Correct |
148 ms |
79608 KB |
Output is correct |
| 32 |
Incorrect |
156 ms |
79608 KB |
Output isn't correct |
| 33 |
Incorrect |
128 ms |
79684 KB |
Output isn't correct |
| 34 |
Correct |
204 ms |
80248 KB |
Output is correct |
| 35 |
Incorrect |
138 ms |
79736 KB |
Output isn't correct |
| 36 |
Correct |
280 ms |
80632 KB |
Output is correct |
| 37 |
Incorrect |
160 ms |
80760 KB |
Output isn't correct |
| 38 |
Correct |
221 ms |
79736 KB |
Output is correct |
| 39 |
Incorrect |
140 ms |
79736 KB |
Output isn't correct |
| 40 |
Correct |
211 ms |
79604 KB |
Output is correct |
| 41 |
Correct |
186 ms |
80248 KB |
Output is correct |
| 42 |
Incorrect |
248 ms |
79864 KB |
Output isn't correct |
