#include <bits/stdc++.h>
#define N 100050
using namespace std;
int n, q, p[N], dp[10000005], prox[10000005];
int solve(int x)
{
if(!x) return 0;
if(dp[x] != -1) return dp[x];
int ans = -2000000000, opt = 0;
for(int i = 1; i <= n; i++)
{
if(x % p[i] == 0) continue;
if(x % p[i] > ans)
{
ans = x % p[i];
opt = i;
}
}
//prox[x] = opt ? solve(x - ans) + 1: 2000000000;
return dp[x] = opt ? solve(x - ans) + 1: 2000000000;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>q;
for(int i = 1; i <= n; i++) cin>>p[i];
memset(dp, -1, sizeof dp);
for(int i = 1, x; i <= q; i++)
{
cin>>x;
int s = solve(x);
if(s >= 2000000000) cout<<"oo\n";
else cout<<s<<"\n";
//print(x);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
39416 KB |
Output is correct |
| 2 |
Correct |
38 ms |
39660 KB |
Output is correct |
| 3 |
Correct |
41 ms |
39660 KB |
Output is correct |
| 4 |
Correct |
49 ms |
39668 KB |
Output is correct |
| 5 |
Correct |
38 ms |
39764 KB |
Output is correct |
| 6 |
Correct |
39 ms |
39764 KB |
Output is correct |
| 7 |
Correct |
40 ms |
39764 KB |
Output is correct |
| 8 |
Correct |
39 ms |
39764 KB |
Output is correct |
| 9 |
Correct |
39 ms |
39816 KB |
Output is correct |
| 10 |
Correct |
40 ms |
39848 KB |
Output is correct |
| 11 |
Correct |
35 ms |
39860 KB |
Output is correct |
| 12 |
Correct |
38 ms |
39868 KB |
Output is correct |
| 13 |
Correct |
48 ms |
39868 KB |
Output is correct |
| 14 |
Correct |
92 ms |
40012 KB |
Output is correct |
| 15 |
Correct |
39 ms |
40012 KB |
Output is correct |
| 16 |
Correct |
38 ms |
40012 KB |
Output is correct |
| 17 |
Correct |
54 ms |
40012 KB |
Output is correct |
| 18 |
Correct |
46 ms |
40020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
40068 KB |
Output is correct |
| 2 |
Correct |
52 ms |
41176 KB |
Output is correct |
| 3 |
Correct |
56 ms |
41496 KB |
Output is correct |
| 4 |
Correct |
40 ms |
41496 KB |
Output is correct |
| 5 |
Correct |
46 ms |
41496 KB |
Output is correct |
| 6 |
Correct |
39 ms |
41496 KB |
Output is correct |
| 7 |
Correct |
40 ms |
41496 KB |
Output is correct |
| 8 |
Correct |
39 ms |
41496 KB |
Output is correct |
| 9 |
Correct |
50 ms |
41748 KB |
Output is correct |
| 10 |
Correct |
44 ms |
41748 KB |
Output is correct |
| 11 |
Correct |
47 ms |
41748 KB |
Output is correct |
| 12 |
Correct |
39 ms |
41748 KB |
Output is correct |
| 13 |
Correct |
42 ms |
41748 KB |
Output is correct |
| 14 |
Correct |
42 ms |
41748 KB |
Output is correct |
| 15 |
Correct |
44 ms |
41748 KB |
Output is correct |
| 16 |
Correct |
53 ms |
41748 KB |
Output is correct |
| 17 |
Correct |
42 ms |
41748 KB |
Output is correct |
| 18 |
Correct |
53 ms |
41748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1083 ms |
41748 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1092 ms |
41748 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1095 ms |
41748 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1092 ms |
42072 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1072 ms |
42072 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1082 ms |
42072 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1084 ms |
42148 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1082 ms |
42148 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1083 ms |
42148 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1004 ms |
42148 KB |
Time limit exceeded |
| 11 |
Correct |
988 ms |
42148 KB |
Output is correct |
| 12 |
Execution timed out |
1097 ms |
42148 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1084 ms |
42232 KB |
Time limit exceeded |
| 14 |
Correct |
115 ms |
44152 KB |
Output is correct |
| 15 |
Execution timed out |
1087 ms |
44152 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1086 ms |
44152 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1085 ms |
44152 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1080 ms |
44152 KB |
Time limit exceeded |
| 19 |
Correct |
924 ms |
44152 KB |
Output is correct |
| 20 |
Execution timed out |
1075 ms |
44152 KB |
Time limit exceeded |
| 21 |
Correct |
143 ms |
44636 KB |
Output is correct |
| 22 |
Execution timed out |
1085 ms |
44636 KB |
Time limit exceeded |
| 23 |
Execution timed out |
1085 ms |
44636 KB |
Time limit exceeded |
| 24 |
Correct |
811 ms |
44940 KB |
Output is correct |
| 25 |
Execution timed out |
1087 ms |
45340 KB |
Time limit exceeded |
| 26 |
Execution timed out |
1086 ms |
45676 KB |
Time limit exceeded |
| 27 |
Execution timed out |
1089 ms |
45808 KB |
Time limit exceeded |
| 28 |
Correct |
546 ms |
46452 KB |
Output is correct |
| 29 |
Execution timed out |
1077 ms |
46576 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1087 ms |
46576 KB |
Time limit exceeded |
| 31 |
Execution timed out |
1087 ms |
46836 KB |
Time limit exceeded |
| 32 |
Execution timed out |
1079 ms |
47352 KB |
Time limit exceeded |
| 33 |
Correct |
763 ms |
48244 KB |
Output is correct |
| 34 |
Execution timed out |
1084 ms |
48248 KB |
Time limit exceeded |
| 35 |
Execution timed out |
1040 ms |
48716 KB |
Time limit exceeded |
| 36 |
Execution timed out |
1081 ms |
48852 KB |
Time limit exceeded |
| 37 |
Execution timed out |
1075 ms |
48852 KB |
Time limit exceeded |
| 38 |
Execution timed out |
1073 ms |
48852 KB |
Time limit exceeded |
| 39 |
Execution timed out |
1088 ms |
49624 KB |
Time limit exceeded |
| 40 |
Execution timed out |
1088 ms |
49624 KB |
Time limit exceeded |
| 41 |
Execution timed out |
1087 ms |
49760 KB |
Time limit exceeded |
| 42 |
Execution timed out |
1073 ms |
50276 KB |
Time limit exceeded |
