#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define pdb pair <double, double>
#define YES cout<<"YES"
#define NO cout<<"NO"
#define endl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll>
#define mp make_pair
#define pb push_back
#define f first
#define s second
using namespace std;
const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=LLONG_MAX;
const ll N=1e5, MAXN=1e7;
ll n, q;
ll a[N+5];
ll ans[MAXN+5];
ll product=1;
void input()
{
cin >> n >> q;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
product*=a[i];
if(product>=MAXN) product=MAXN;
}
}
void solve()
{
for(int i = 1; i <= MAXN; i++)
{
ans[i]=INFINF;
if(i>=product) continue;
for(int j = n; j >= 1; j--)
{
if(i%a[j])
{
ans[i]=min(ans[i], ans[i-i%a[j]]+1);
}
}
}
while(q--)
{
ll x;
cin >> x;
if(ans[x]==INFINF) cout << "oo";
else cout << ans[x];
endl;
}
}
int main()
{
// auto start_time = chrono::high_resolution_clock::now();
// freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
input();
solve();
// auto end_time = chrono::high_resolution_clock::now();
// double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
// cout << "\n[ " << duration << " ms ]\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
78564 KB |
Output is correct |
| 2 |
Execution timed out |
1093 ms |
27820 KB |
Time limit exceeded |
| 3 |
Correct |
44 ms |
78580 KB |
Output is correct |
| 4 |
Execution timed out |
1071 ms |
16048 KB |
Time limit exceeded |
| 5 |
Correct |
852 ms |
78548 KB |
Output is correct |
| 6 |
Correct |
48 ms |
78540 KB |
Output is correct |
| 7 |
Correct |
44 ms |
78500 KB |
Output is correct |
| 8 |
Correct |
75 ms |
78520 KB |
Output is correct |
| 9 |
Correct |
955 ms |
78552 KB |
Output is correct |
| 10 |
Execution timed out |
1046 ms |
43448 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1077 ms |
38384 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1089 ms |
12760 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1083 ms |
1580 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1094 ms |
1732 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1049 ms |
32668 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1063 ms |
26692 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1099 ms |
15260 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1099 ms |
16572 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
536 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1087 ms |
1036 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1088 ms |
1004 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1096 ms |
776 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1057 ms |
740 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1060 ms |
1516 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1061 ms |
628 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1086 ms |
1784 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1072 ms |
1004 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1092 ms |
884 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1083 ms |
664 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1075 ms |
1124 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1092 ms |
888 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1045 ms |
820 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1078 ms |
676 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1078 ms |
1100 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1085 ms |
840 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1087 ms |
1220 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1042 ms |
724 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1086 ms |
856 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1086 ms |
724 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1050 ms |
888 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1031 ms |
1108 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1071 ms |
480 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1055 ms |
1100 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1079 ms |
708 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1099 ms |
724 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1089 ms |
428 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1082 ms |
892 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1092 ms |
660 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1085 ms |
604 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1091 ms |
35700 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1085 ms |
732 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1080 ms |
608 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1089 ms |
808 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1076 ms |
748 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1094 ms |
684 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1093 ms |
728 KB |
Time limit exceeded |
| 21 |
Execution timed out |
1069 ms |
12400 KB |
Time limit exceeded |
| 22 |
Execution timed out |
1087 ms |
1108 KB |
Time limit exceeded |
| 23 |
Execution timed out |
1083 ms |
700 KB |
Time limit exceeded |
| 24 |
Execution timed out |
1079 ms |
1748 KB |
Time limit exceeded |
| 25 |
Execution timed out |
1083 ms |
928 KB |
Time limit exceeded |
| 26 |
Execution timed out |
1078 ms |
880 KB |
Time limit exceeded |
| 27 |
Execution timed out |
1090 ms |
1220 KB |
Time limit exceeded |
| 28 |
Execution timed out |
1097 ms |
2000 KB |
Time limit exceeded |
| 29 |
Execution timed out |
1091 ms |
1100 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1085 ms |
992 KB |
Time limit exceeded |
| 31 |
Execution timed out |
1081 ms |
904 KB |
Time limit exceeded |
| 32 |
Execution timed out |
1088 ms |
1108 KB |
Time limit exceeded |
| 33 |
Execution timed out |
1078 ms |
1700 KB |
Time limit exceeded |
| 34 |
Execution timed out |
1098 ms |
1100 KB |
Time limit exceeded |
| 35 |
Execution timed out |
1096 ms |
1156 KB |
Time limit exceeded |
| 36 |
Execution timed out |
1086 ms |
1036 KB |
Time limit exceeded |
| 37 |
Execution timed out |
1080 ms |
1096 KB |
Time limit exceeded |
| 38 |
Execution timed out |
1078 ms |
608 KB |
Time limit exceeded |
| 39 |
Execution timed out |
1092 ms |
1180 KB |
Time limit exceeded |
| 40 |
Execution timed out |
1076 ms |
664 KB |
Time limit exceeded |
| 41 |
Execution timed out |
1088 ms |
1108 KB |
Time limit exceeded |
| 42 |
Execution timed out |
1090 ms |
848 KB |
Time limit exceeded |
