#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int n, q;
int tobest[10000005];
int last[10000005];
int ans[10000005];
int ask[100005], p[100005];
int maxsolved=0, maxask=0;
bool used[10000005];
void eras()
{
for(int i=1; i<=n; i++)
{
if(p[i]!=p[i-1])
{
for(int j=0; j<=maxask; j+=p[i])
{
last[j]=max(last[j], j+p[i]-1);
}
}
}
}
void solve()
{
int j=0;
tobest[0]=p[n]-1;
for(int i=0; i<=10000000; i++)
{
if(tobest[i]==0) return;
if(i>0) j=tobest[j-1]+1;
for(int k=j; k<=tobest[i]; k++)
{
if(k>maxask) return;
tobest[i+1]=max(tobest[i+1], last[k]);
ans[k]=i;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1; i<=n; i++)
{
cin>>p[i];
}
sort(p+1, p+n+1);
for(int i=1; i<=q; i++)
{
cin>>ask[i];
maxask=max(maxask, ask[i]);
}
eras();
solve();
// for(int i=0; i<=5; i++)
// {
// cout<<tobest[i]<<endl;
// }
for(int i=1; i<=q; i++)
{
if(ans[ask[i]]==0) cout<<"oo\n";
else cout<<ans[i]+1<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
4 ms |
508 KB |
Output isn't correct |
| 8 |
Incorrect |
4 ms |
508 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 11 |
Incorrect |
1 ms |
504 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 13 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 14 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
508 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 17 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 18 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
168 ms |
77776 KB |
Output is correct |
| 2 |
Correct |
123 ms |
71160 KB |
Output is correct |
| 3 |
Incorrect |
123 ms |
37496 KB |
Output isn't correct |
| 4 |
Correct |
631 ms |
71268 KB |
Output is correct |
| 5 |
Incorrect |
53 ms |
20856 KB |
Output isn't correct |
| 6 |
Correct |
118 ms |
27668 KB |
Output is correct |
| 7 |
Correct |
171 ms |
77812 KB |
Output is correct |
| 8 |
Correct |
272 ms |
29764 KB |
Output is correct |
| 9 |
Correct |
52 ms |
21112 KB |
Output is correct |
| 10 |
Incorrect |
116 ms |
37548 KB |
Output isn't correct |
| 11 |
Correct |
361 ms |
78812 KB |
Output is correct |
| 12 |
Execution timed out |
1018 ms |
67316 KB |
Time limit exceeded |
| 13 |
Correct |
206 ms |
78072 KB |
Output is correct |
| 14 |
Correct |
572 ms |
71148 KB |
Output is correct |
| 15 |
Correct |
65 ms |
25720 KB |
Output is correct |
| 16 |
Correct |
127 ms |
71160 KB |
Output is correct |
| 17 |
Execution timed out |
1066 ms |
67756 KB |
Time limit exceeded |
| 18 |
Correct |
263 ms |
79096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
329 ms |
79228 KB |
Output isn't correct |
| 2 |
Incorrect |
387 ms |
79096 KB |
Output isn't correct |
| 3 |
Incorrect |
235 ms |
56312 KB |
Output isn't correct |
| 4 |
Incorrect |
766 ms |
79444 KB |
Output isn't correct |
| 5 |
Incorrect |
167 ms |
79632 KB |
Output isn't correct |
| 6 |
Incorrect |
681 ms |
79480 KB |
Output isn't correct |
| 7 |
Correct |
168 ms |
56312 KB |
Output is correct |
| 8 |
Incorrect |
312 ms |
79136 KB |
Output isn't correct |
| 9 |
Incorrect |
318 ms |
79040 KB |
Output isn't correct |
| 10 |
Incorrect |
818 ms |
78752 KB |
Output isn't correct |
| 11 |
Incorrect |
836 ms |
78968 KB |
Output isn't correct |
| 12 |
Incorrect |
943 ms |
78932 KB |
Output isn't correct |
| 13 |
Correct |
163 ms |
40952 KB |
Output is correct |
| 14 |
Execution timed out |
1060 ms |
26856 KB |
Time limit exceeded |
| 15 |
Incorrect |
933 ms |
78964 KB |
Output isn't correct |
| 16 |
Incorrect |
973 ms |
78848 KB |
Output isn't correct |
| 17 |
Incorrect |
321 ms |
78984 KB |
Output isn't correct |
| 18 |
Incorrect |
379 ms |
79096 KB |
Output isn't correct |
| 19 |
Incorrect |
189 ms |
78840 KB |
Output isn't correct |
| 20 |
Incorrect |
252 ms |
56296 KB |
Output isn't correct |
| 21 |
Execution timed out |
1077 ms |
45080 KB |
Time limit exceeded |
| 22 |
Incorrect |
351 ms |
79608 KB |
Output isn't correct |
| 23 |
Incorrect |
214 ms |
79516 KB |
Output isn't correct |
| 24 |
Incorrect |
691 ms |
79432 KB |
Output isn't correct |
| 25 |
Execution timed out |
1078 ms |
73964 KB |
Time limit exceeded |
| 26 |
Incorrect |
742 ms |
79372 KB |
Output isn't correct |
| 27 |
Correct |
240 ms |
56312 KB |
Output is correct |
| 28 |
Incorrect |
653 ms |
79480 KB |
Output isn't correct |
| 29 |
Incorrect |
332 ms |
79736 KB |
Output isn't correct |
| 30 |
Incorrect |
322 ms |
79608 KB |
Output isn't correct |
| 31 |
Incorrect |
351 ms |
79240 KB |
Output isn't correct |
| 32 |
Incorrect |
851 ms |
79480 KB |
Output isn't correct |
| 33 |
Incorrect |
453 ms |
79344 KB |
Output isn't correct |
| 34 |
Correct |
169 ms |
56332 KB |
Output is correct |
| 35 |
Incorrect |
592 ms |
79368 KB |
Output isn't correct |
| 36 |
Incorrect |
390 ms |
79652 KB |
Output isn't correct |
| 37 |
Incorrect |
191 ms |
79608 KB |
Output isn't correct |
| 38 |
Incorrect |
696 ms |
79412 KB |
Output isn't correct |
| 39 |
Incorrect |
628 ms |
79480 KB |
Output isn't correct |
| 40 |
Incorrect |
508 ms |
79412 KB |
Output isn't correct |
| 41 |
Incorrect |
138 ms |
56388 KB |
Output isn't correct |
| 42 |
Execution timed out |
1079 ms |
69136 KB |
Time limit exceeded |
