/*
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;
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) 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 |
92 ms |
78712 KB |
Output is correct |
| 2 |
Correct |
131 ms |
78716 KB |
Output is correct |
| 3 |
Correct |
117 ms |
78776 KB |
Output is correct |
| 4 |
Correct |
100 ms |
78776 KB |
Output is correct |
| 5 |
Correct |
117 ms |
78776 KB |
Output is correct |
| 6 |
Correct |
105 ms |
78828 KB |
Output is correct |
| 7 |
Correct |
111 ms |
78896 KB |
Output is correct |
| 8 |
Correct |
117 ms |
78896 KB |
Output is correct |
| 9 |
Correct |
144 ms |
78896 KB |
Output is correct |
| 10 |
Correct |
188 ms |
78896 KB |
Output is correct |
| 11 |
Correct |
169 ms |
78896 KB |
Output is correct |
| 12 |
Correct |
108 ms |
78896 KB |
Output is correct |
| 13 |
Correct |
307 ms |
78896 KB |
Output is correct |
| 14 |
Correct |
281 ms |
78928 KB |
Output is correct |
| 15 |
Correct |
155 ms |
78928 KB |
Output is correct |
| 16 |
Correct |
139 ms |
78928 KB |
Output is correct |
| 17 |
Correct |
152 ms |
78984 KB |
Output is correct |
| 18 |
Correct |
107 ms |
78984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
79020 KB |
Output is correct |
| 2 |
Correct |
120 ms |
79276 KB |
Output is correct |
| 3 |
Correct |
378 ms |
79276 KB |
Output is correct |
| 4 |
Correct |
143 ms |
79276 KB |
Output is correct |
| 5 |
Correct |
273 ms |
79276 KB |
Output is correct |
| 6 |
Correct |
145 ms |
79276 KB |
Output is correct |
| 7 |
Correct |
137 ms |
79276 KB |
Output is correct |
| 8 |
Correct |
175 ms |
79276 KB |
Output is correct |
| 9 |
Correct |
321 ms |
79276 KB |
Output is correct |
| 10 |
Correct |
340 ms |
79276 KB |
Output is correct |
| 11 |
Incorrect |
390 ms |
79276 KB |
Output isn't correct |
| 12 |
Correct |
218 ms |
79276 KB |
Output is correct |
| 13 |
Correct |
125 ms |
79276 KB |
Output is correct |
| 14 |
Correct |
164 ms |
79276 KB |
Output is correct |
| 15 |
Correct |
325 ms |
79276 KB |
Output is correct |
| 16 |
Correct |
140 ms |
79388 KB |
Output is correct |
| 17 |
Correct |
285 ms |
79388 KB |
Output is correct |
| 18 |
Correct |
316 ms |
79404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
333 ms |
79404 KB |
Output is correct |
| 2 |
Correct |
427 ms |
79404 KB |
Output is correct |
| 3 |
Correct |
427 ms |
79404 KB |
Output is correct |
| 4 |
Incorrect |
251 ms |
79404 KB |
Output isn't correct |
| 5 |
Incorrect |
186 ms |
79492 KB |
Output isn't correct |
| 6 |
Correct |
343 ms |
79492 KB |
Output is correct |
| 7 |
Correct |
280 ms |
79492 KB |
Output is correct |
| 8 |
Correct |
341 ms |
79492 KB |
Output is correct |
| 9 |
Correct |
324 ms |
79492 KB |
Output is correct |
| 10 |
Correct |
257 ms |
79492 KB |
Output is correct |
| 11 |
Incorrect |
241 ms |
79492 KB |
Output isn't correct |
| 12 |
Correct |
309 ms |
79492 KB |
Output is correct |
| 13 |
Correct |
404 ms |
79492 KB |
Output is correct |
| 14 |
Correct |
222 ms |
79660 KB |
Output is correct |
| 15 |
Incorrect |
323 ms |
79660 KB |
Output isn't correct |
| 16 |
Correct |
324 ms |
79660 KB |
Output is correct |
| 17 |
Correct |
308 ms |
79660 KB |
Output is correct |
| 18 |
Correct |
384 ms |
79660 KB |
Output is correct |
| 19 |
Incorrect |
124 ms |
79660 KB |
Output isn't correct |
| 20 |
Correct |
346 ms |
79660 KB |
Output is correct |
| 21 |
Incorrect |
264 ms |
79660 KB |
Output isn't correct |
| 22 |
Correct |
427 ms |
79660 KB |
Output is correct |
| 23 |
Correct |
200 ms |
79660 KB |
Output is correct |
| 24 |
Correct |
164 ms |
79660 KB |
Output is correct |
| 25 |
Correct |
273 ms |
79660 KB |
Output is correct |
| 26 |
Incorrect |
251 ms |
79660 KB |
Output isn't correct |
| 27 |
Correct |
455 ms |
79660 KB |
Output is correct |
| 28 |
Incorrect |
151 ms |
79660 KB |
Output isn't correct |
| 29 |
Correct |
410 ms |
79660 KB |
Output is correct |
| 30 |
Correct |
380 ms |
79660 KB |
Output is correct |
| 31 |
Correct |
195 ms |
79660 KB |
Output is correct |
| 32 |
Incorrect |
210 ms |
79660 KB |
Output isn't correct |
| 33 |
Incorrect |
145 ms |
79660 KB |
Output isn't correct |
| 34 |
Correct |
313 ms |
79660 KB |
Output is correct |
| 35 |
Incorrect |
161 ms |
79660 KB |
Output isn't correct |
| 36 |
Correct |
402 ms |
79660 KB |
Output is correct |
| 37 |
Incorrect |
182 ms |
79660 KB |
Output isn't correct |
| 38 |
Correct |
351 ms |
79660 KB |
Output is correct |
| 39 |
Correct |
154 ms |
79660 KB |
Output is correct |
| 40 |
Correct |
287 ms |
79660 KB |
Output is correct |
| 41 |
Correct |
225 ms |
79660 KB |
Output is correct |
| 42 |
Correct |
307 ms |
79660 KB |
Output is correct |
