/*
There is a simple solution with upper bound on the time equal to O(MAX * log(log(MAX)) * log(MAX)) with DP and maintaining a heap. Probably the actual complexity is smaller.
Unfortunately this was too slow, but we can notice that there is monotonicity in the answers and so if at each step we remove the largest number of people we will have an optimal strategy.
This also means we can remove the heap from the dp and just find the largest transition.
*/
#include <bits/stdc++.h>
#define endl '\n'
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int B = (int)1e7 + 42;
const int inf = B + 42;
int n, q;
int dp[B + 42];
int a[MAXN], trans[B + 42];
void read()
{
cin >> n >> q;
for(int i = 0; i < n; i++)
cin >> a[i];
}
void solve()
{
dp[0] = 0;
int64_t prod = 1;
for(int i = 0; i < n; i++) prod = (prod > B) ? prod : (prod * 1ll * a[i]);
for(int i = 1; i < a[n - 1]; i++) dp[i] = 1;
for(int i = a[n - 1]; i <= B; i++) dp[i] = inf;
for(int i = 0; i < n; i++)
for(int j = a[i] - 1; j <= B; j += a[i])
trans[j] = a[i] - 1;
for(int i = B; i >= 0; i--)
chkmax(trans[i], trans[i + 1] - 1);
for(int d = a[n - 1]; d <= B; d++)
chkmin(dp[d], 1 + dp[d - trans[d]]);
while(q--)
{
int x;
cin >> x;
if(dp[x] >= inf || x >= prod) cout << "oo" << endl;
else cout << dp[x] << endl;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
read();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
78712 KB |
Output is correct |
| 2 |
Correct |
148 ms |
78860 KB |
Output is correct |
| 3 |
Correct |
126 ms |
78860 KB |
Output is correct |
| 4 |
Correct |
109 ms |
78860 KB |
Output is correct |
| 5 |
Correct |
142 ms |
78860 KB |
Output is correct |
| 6 |
Correct |
120 ms |
78860 KB |
Output is correct |
| 7 |
Correct |
131 ms |
78860 KB |
Output is correct |
| 8 |
Correct |
132 ms |
78860 KB |
Output is correct |
| 9 |
Correct |
159 ms |
78860 KB |
Output is correct |
| 10 |
Correct |
192 ms |
78876 KB |
Output is correct |
| 11 |
Correct |
184 ms |
78876 KB |
Output is correct |
| 12 |
Correct |
116 ms |
78968 KB |
Output is correct |
| 13 |
Correct |
336 ms |
78968 KB |
Output is correct |
| 14 |
Correct |
337 ms |
78968 KB |
Output is correct |
| 15 |
Correct |
156 ms |
78968 KB |
Output is correct |
| 16 |
Correct |
145 ms |
78968 KB |
Output is correct |
| 17 |
Correct |
160 ms |
78968 KB |
Output is correct |
| 18 |
Correct |
126 ms |
78968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
79004 KB |
Output is correct |
| 2 |
Correct |
120 ms |
79248 KB |
Output is correct |
| 3 |
Correct |
411 ms |
79248 KB |
Output is correct |
| 4 |
Correct |
151 ms |
79248 KB |
Output is correct |
| 5 |
Correct |
273 ms |
79248 KB |
Output is correct |
| 6 |
Correct |
143 ms |
79248 KB |
Output is correct |
| 7 |
Correct |
144 ms |
79248 KB |
Output is correct |
| 8 |
Correct |
168 ms |
79248 KB |
Output is correct |
| 9 |
Correct |
334 ms |
79260 KB |
Output is correct |
| 10 |
Correct |
397 ms |
79260 KB |
Output is correct |
| 11 |
Incorrect |
399 ms |
79260 KB |
Output isn't correct |
| 12 |
Correct |
228 ms |
79260 KB |
Output is correct |
| 13 |
Correct |
118 ms |
79260 KB |
Output is correct |
| 14 |
Correct |
172 ms |
79260 KB |
Output is correct |
| 15 |
Correct |
320 ms |
79260 KB |
Output is correct |
| 16 |
Correct |
138 ms |
79372 KB |
Output is correct |
| 17 |
Correct |
331 ms |
79372 KB |
Output is correct |
| 18 |
Correct |
304 ms |
79404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
325 ms |
79404 KB |
Output is correct |
| 2 |
Correct |
400 ms |
79404 KB |
Output is correct |
| 3 |
Correct |
396 ms |
79420 KB |
Output is correct |
| 4 |
Incorrect |
240 ms |
79420 KB |
Output isn't correct |
| 5 |
Incorrect |
156 ms |
79548 KB |
Output isn't correct |
| 6 |
Correct |
361 ms |
79548 KB |
Output is correct |
| 7 |
Correct |
280 ms |
79548 KB |
Output is correct |
| 8 |
Correct |
314 ms |
79548 KB |
Output is correct |
| 9 |
Correct |
275 ms |
79548 KB |
Output is correct |
| 10 |
Correct |
242 ms |
79548 KB |
Output is correct |
| 11 |
Incorrect |
220 ms |
79548 KB |
Output isn't correct |
| 12 |
Correct |
315 ms |
79548 KB |
Output is correct |
| 13 |
Correct |
415 ms |
79548 KB |
Output is correct |
| 14 |
Correct |
225 ms |
79548 KB |
Output is correct |
| 15 |
Incorrect |
333 ms |
79548 KB |
Output isn't correct |
| 16 |
Correct |
372 ms |
79548 KB |
Output is correct |
| 17 |
Correct |
319 ms |
79548 KB |
Output is correct |
| 18 |
Correct |
385 ms |
79548 KB |
Output is correct |
| 19 |
Incorrect |
114 ms |
79548 KB |
Output isn't correct |
| 20 |
Correct |
369 ms |
79548 KB |
Output is correct |
| 21 |
Incorrect |
267 ms |
79548 KB |
Output isn't correct |
| 22 |
Correct |
367 ms |
79548 KB |
Output is correct |
| 23 |
Correct |
162 ms |
79548 KB |
Output is correct |
| 24 |
Correct |
156 ms |
79548 KB |
Output is correct |
| 25 |
Correct |
284 ms |
79548 KB |
Output is correct |
| 26 |
Incorrect |
248 ms |
79548 KB |
Output isn't correct |
| 27 |
Correct |
432 ms |
79548 KB |
Output is correct |
| 28 |
Incorrect |
152 ms |
79548 KB |
Output isn't correct |
| 29 |
Correct |
404 ms |
79548 KB |
Output is correct |
| 30 |
Correct |
368 ms |
79548 KB |
Output is correct |
| 31 |
Correct |
192 ms |
79548 KB |
Output is correct |
| 32 |
Incorrect |
182 ms |
79548 KB |
Output isn't correct |
| 33 |
Incorrect |
128 ms |
79548 KB |
Output isn't correct |
| 34 |
Correct |
282 ms |
79548 KB |
Output is correct |
| 35 |
Incorrect |
147 ms |
79548 KB |
Output isn't correct |
| 36 |
Correct |
414 ms |
79548 KB |
Output is correct |
| 37 |
Incorrect |
175 ms |
79552 KB |
Output isn't correct |
| 38 |
Correct |
344 ms |
79552 KB |
Output is correct |
| 39 |
Correct |
167 ms |
79552 KB |
Output is correct |
| 40 |
Correct |
302 ms |
79552 KB |
Output is correct |
| 41 |
Correct |
243 ms |
79552 KB |
Output is correct |
| 42 |
Correct |
372 ms |
79552 KB |
Output is correct |
