#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[30000001];
int dp[30000001];
//vector<int> fac[30000001];
int main(){
memset(ma,0,sizeof(ma));
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<30000001;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<30000001;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 |
228 ms |
235128 KB |
Output is correct |
| 2 |
Correct |
280 ms |
235212 KB |
Output is correct |
| 3 |
Correct |
254 ms |
235384 KB |
Output is correct |
| 4 |
Correct |
222 ms |
235128 KB |
Output is correct |
| 5 |
Correct |
291 ms |
235256 KB |
Output is correct |
| 6 |
Correct |
225 ms |
235256 KB |
Output is correct |
| 7 |
Correct |
247 ms |
235128 KB |
Output is correct |
| 8 |
Correct |
259 ms |
235132 KB |
Output is correct |
| 9 |
Correct |
318 ms |
235256 KB |
Output is correct |
| 10 |
Correct |
360 ms |
235128 KB |
Output is correct |
| 11 |
Correct |
365 ms |
235256 KB |
Output is correct |
| 12 |
Correct |
208 ms |
235128 KB |
Output is correct |
| 13 |
Correct |
544 ms |
235256 KB |
Output is correct |
| 14 |
Correct |
546 ms |
235128 KB |
Output is correct |
| 15 |
Correct |
306 ms |
235128 KB |
Output is correct |
| 16 |
Correct |
273 ms |
235208 KB |
Output is correct |
| 17 |
Correct |
309 ms |
235360 KB |
Output is correct |
| 18 |
Correct |
217 ms |
235256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
286 ms |
235256 KB |
Output is correct |
| 2 |
Correct |
339 ms |
235640 KB |
Output is correct |
| 3 |
Correct |
689 ms |
235456 KB |
Output is correct |
| 4 |
Correct |
368 ms |
235128 KB |
Output is correct |
| 5 |
Correct |
546 ms |
235512 KB |
Output is correct |
| 6 |
Correct |
282 ms |
235208 KB |
Output is correct |
| 7 |
Correct |
275 ms |
235256 KB |
Output is correct |
| 8 |
Correct |
375 ms |
235128 KB |
Output is correct |
| 9 |
Correct |
603 ms |
235512 KB |
Output is correct |
| 10 |
Correct |
720 ms |
235640 KB |
Output is correct |
| 11 |
Incorrect |
697 ms |
235384 KB |
Output isn't correct |
| 12 |
Correct |
432 ms |
235256 KB |
Output is correct |
| 13 |
Correct |
253 ms |
235128 KB |
Output is correct |
| 14 |
Correct |
377 ms |
235256 KB |
Output is correct |
| 15 |
Correct |
573 ms |
235340 KB |
Output is correct |
| 16 |
Correct |
325 ms |
235512 KB |
Output is correct |
| 17 |
Correct |
585 ms |
235256 KB |
Output is correct |
| 18 |
Correct |
621 ms |
235512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
590 ms |
235568 KB |
Output is correct |
| 2 |
Correct |
726 ms |
235384 KB |
Output is correct |
| 3 |
Correct |
718 ms |
235640 KB |
Output is correct |
| 4 |
Incorrect |
459 ms |
235384 KB |
Output isn't correct |
| 5 |
Incorrect |
380 ms |
235768 KB |
Output isn't correct |
| 6 |
Correct |
587 ms |
235516 KB |
Output is correct |
| 7 |
Correct |
583 ms |
235640 KB |
Output is correct |
| 8 |
Correct |
588 ms |
235384 KB |
Output is correct |
| 9 |
Correct |
604 ms |
235512 KB |
Output is correct |
| 10 |
Correct |
523 ms |
235256 KB |
Output is correct |
| 11 |
Incorrect |
477 ms |
235256 KB |
Output isn't correct |
| 12 |
Correct |
541 ms |
235336 KB |
Output is correct |
| 13 |
Correct |
676 ms |
235640 KB |
Output is correct |
| 14 |
Correct |
406 ms |
235768 KB |
Output is correct |
| 15 |
Incorrect |
576 ms |
235324 KB |
Output isn't correct |
| 16 |
Correct |
629 ms |
235256 KB |
Output is correct |
| 17 |
Correct |
578 ms |
235384 KB |
Output is correct |
| 18 |
Correct |
707 ms |
235512 KB |
Output is correct |
| 19 |
Incorrect |
269 ms |
235256 KB |
Output isn't correct |
| 20 |
Correct |
724 ms |
235528 KB |
Output is correct |
| 21 |
Incorrect |
444 ms |
235896 KB |
Output isn't correct |
| 22 |
Correct |
745 ms |
235768 KB |
Output is correct |
| 23 |
Correct |
380 ms |
235472 KB |
Output is correct |
| 24 |
Correct |
299 ms |
235512 KB |
Output is correct |
| 25 |
Incorrect |
510 ms |
235640 KB |
Output isn't correct |
| 26 |
Incorrect |
463 ms |
235512 KB |
Output isn't correct |
| 27 |
Correct |
773 ms |
235768 KB |
Output is correct |
| 28 |
Incorrect |
306 ms |
235512 KB |
Output isn't correct |
| 29 |
Correct |
733 ms |
235820 KB |
Output is correct |
| 30 |
Correct |
649 ms |
235768 KB |
Output is correct |
| 31 |
Correct |
376 ms |
235376 KB |
Output is correct |
| 32 |
Incorrect |
411 ms |
235848 KB |
Output isn't correct |
| 33 |
Incorrect |
257 ms |
235384 KB |
Output isn't correct |
| 34 |
Correct |
593 ms |
235768 KB |
Output is correct |
| 35 |
Incorrect |
334 ms |
235512 KB |
Output isn't correct |
| 36 |
Correct |
783 ms |
235740 KB |
Output is correct |
| 37 |
Incorrect |
377 ms |
235896 KB |
Output isn't correct |
| 38 |
Correct |
591 ms |
235640 KB |
Output is correct |
| 39 |
Incorrect |
342 ms |
235512 KB |
Output isn't correct |
| 40 |
Correct |
519 ms |
235512 KB |
Output is correct |
| 41 |
Correct |
518 ms |
235640 KB |
Output is correct |
| 42 |
Incorrect |
622 ms |
235640 KB |
Output isn't correct |
