#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;;
const int lim = 1e7 + 3;
const int inf = 1e9 + 9;
int p[N], m, q;
int dp[lim];
string s;
int dfs(int u)
{
if(dp[u] != inf)
return dp[u];
if(u == 0)
return 0;
int cnt = 0;
for(int i = m; i >= 1; i--)
{
if(p[i] > u)
{
dp[u] = 1;
return dp[u];
}
if(u % p[i] == 0 && u != 0)
{
cnt ++;
continue;
}
dp[u] = min(dp[u], dfs(u - u % p[i]) + 1);
}
if(cnt == m)
{
dp[u] = inf - 1;
return inf - 1;
}
return dp[u];
}
int main()
{
for(int i = 1; i < lim; i++)
{
dp[i] = inf;
}
cin >> m >> q;
for(int i = 1; i <= m; i++)
{
cin >> p[i];
}
sort(p + 1, p + 1 + m);
for(int i = 1; i <= q; i++)
{
int n;
cin >> n;
dfs(n);
if(dp[n] == inf - 1)
cout << "oo\n";
else
cout << dp[n] << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1055 ms |
39416 KB |
Time limit exceeded |
| 2 |
Correct |
39 ms |
39416 KB |
Output is correct |
| 3 |
Correct |
37 ms |
39544 KB |
Output is correct |
| 4 |
Correct |
71 ms |
39544 KB |
Output is correct |
| 5 |
Correct |
36 ms |
39416 KB |
Output is correct |
| 6 |
Execution timed out |
1052 ms |
39420 KB |
Time limit exceeded |
| 7 |
Correct |
36 ms |
39416 KB |
Output is correct |
| 8 |
Correct |
36 ms |
39416 KB |
Output is correct |
| 9 |
Correct |
36 ms |
39416 KB |
Output is correct |
| 10 |
Correct |
40 ms |
39416 KB |
Output is correct |
| 11 |
Correct |
40 ms |
39544 KB |
Output is correct |
| 12 |
Correct |
38 ms |
39416 KB |
Output is correct |
| 13 |
Correct |
45 ms |
39516 KB |
Output is correct |
| 14 |
Correct |
64 ms |
39556 KB |
Output is correct |
| 15 |
Correct |
38 ms |
39544 KB |
Output is correct |
| 16 |
Correct |
39 ms |
39416 KB |
Output is correct |
| 17 |
Correct |
70 ms |
39524 KB |
Output is correct |
| 18 |
Correct |
67 ms |
39420 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1088 ms |
39772 KB |
Time limit exceeded |
| 2 |
Correct |
96 ms |
39800 KB |
Output is correct |
| 3 |
Execution timed out |
1067 ms |
40408 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1081 ms |
39544 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1070 ms |
40660 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1061 ms |
39416 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1058 ms |
39800 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1072 ms |
39516 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1092 ms |
40572 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1048 ms |
40332 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1077 ms |
39800 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1073 ms |
39544 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1069 ms |
39544 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1079 ms |
39544 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1086 ms |
40696 KB |
Time limit exceeded |
| 16 |
Correct |
96 ms |
39800 KB |
Output is correct |
| 17 |
Execution timed out |
1080 ms |
39544 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1085 ms |
40804 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1067 ms |
40752 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1085 ms |
40544 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1083 ms |
40156 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1061 ms |
39544 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1074 ms |
40828 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1071 ms |
39672 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1071 ms |
40672 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1072 ms |
40528 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1080 ms |
40740 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1066 ms |
39636 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1053 ms |
39492 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1073 ms |
39544 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1077 ms |
39544 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1073 ms |
42672 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1076 ms |
39544 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1069 ms |
39672 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1070 ms |
40520 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1077 ms |
40568 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1053 ms |
39564 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1083 ms |
40340 KB |
Time limit exceeded |
| 21 |
Execution timed out |
1076 ms |
40056 KB |
Time limit exceeded |
| 22 |
Execution timed out |
1060 ms |
40740 KB |
Time limit exceeded |
| 23 |
Execution timed out |
1079 ms |
40224 KB |
Time limit exceeded |
| 24 |
Execution timed out |
1091 ms |
39416 KB |
Time limit exceeded |
| 25 |
Execution timed out |
1071 ms |
39568 KB |
Time limit exceeded |
| 26 |
Execution timed out |
1086 ms |
39544 KB |
Time limit exceeded |
| 27 |
Execution timed out |
1078 ms |
40780 KB |
Time limit exceeded |
| 28 |
Execution timed out |
1078 ms |
39416 KB |
Time limit exceeded |
| 29 |
Execution timed out |
1091 ms |
40624 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1069 ms |
40640 KB |
Time limit exceeded |
| 31 |
Execution timed out |
1071 ms |
39544 KB |
Time limit exceeded |
| 32 |
Execution timed out |
1068 ms |
39548 KB |
Time limit exceeded |
| 33 |
Execution timed out |
1084 ms |
39544 KB |
Time limit exceeded |
| 34 |
Execution timed out |
1056 ms |
40828 KB |
Time limit exceeded |
| 35 |
Execution timed out |
1077 ms |
39416 KB |
Time limit exceeded |
| 36 |
Execution timed out |
1069 ms |
40708 KB |
Time limit exceeded |
| 37 |
Execution timed out |
1079 ms |
40696 KB |
Time limit exceeded |
| 38 |
Execution timed out |
1082 ms |
39672 KB |
Time limit exceeded |
| 39 |
Execution timed out |
1068 ms |
39544 KB |
Time limit exceeded |
| 40 |
Execution timed out |
1084 ms |
39672 KB |
Time limit exceeded |
| 41 |
Correct |
276 ms |
40056 KB |
Output is correct |
| 42 |
Execution timed out |
1050 ms |
39572 KB |
Time limit exceeded |
