/*
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()
{
int64_t prod = 1;
for(int i = 0; i < n; i++) prod = (prod > B) ? prod : (prod * 1ll * a[i]);
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 = 1; d <= B; d++)
dp[d] = 1 + dp[d - trans[d]];
while(q--)
{
int x;
cin >> x;
if(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 |
88 ms |
78584 KB |
Output is correct |
| 2 |
Correct |
122 ms |
78584 KB |
Output is correct |
| 3 |
Correct |
108 ms |
78748 KB |
Output is correct |
| 4 |
Correct |
98 ms |
78856 KB |
Output is correct |
| 5 |
Correct |
112 ms |
78960 KB |
Output is correct |
| 6 |
Correct |
131 ms |
78960 KB |
Output is correct |
| 7 |
Correct |
129 ms |
78960 KB |
Output is correct |
| 8 |
Correct |
120 ms |
78960 KB |
Output is correct |
| 9 |
Correct |
136 ms |
78960 KB |
Output is correct |
| 10 |
Correct |
152 ms |
78960 KB |
Output is correct |
| 11 |
Correct |
174 ms |
78960 KB |
Output is correct |
| 12 |
Correct |
105 ms |
78960 KB |
Output is correct |
| 13 |
Correct |
286 ms |
78960 KB |
Output is correct |
| 14 |
Correct |
353 ms |
79068 KB |
Output is correct |
| 15 |
Correct |
135 ms |
79068 KB |
Output is correct |
| 16 |
Correct |
125 ms |
79068 KB |
Output is correct |
| 17 |
Correct |
134 ms |
79068 KB |
Output is correct |
| 18 |
Correct |
98 ms |
79068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
79068 KB |
Output is correct |
| 2 |
Correct |
151 ms |
79220 KB |
Output is correct |
| 3 |
Correct |
391 ms |
79260 KB |
Output is correct |
| 4 |
Correct |
163 ms |
79260 KB |
Output is correct |
| 5 |
Correct |
283 ms |
79260 KB |
Output is correct |
| 6 |
Correct |
133 ms |
79260 KB |
Output is correct |
| 7 |
Correct |
133 ms |
79260 KB |
Output is correct |
| 8 |
Correct |
159 ms |
79260 KB |
Output is correct |
| 9 |
Correct |
323 ms |
79260 KB |
Output is correct |
| 10 |
Correct |
387 ms |
79260 KB |
Output is correct |
| 11 |
Incorrect |
346 ms |
79260 KB |
Output isn't correct |
| 12 |
Correct |
195 ms |
79260 KB |
Output is correct |
| 13 |
Correct |
160 ms |
79260 KB |
Output is correct |
| 14 |
Correct |
140 ms |
79260 KB |
Output is correct |
| 15 |
Correct |
297 ms |
79260 KB |
Output is correct |
| 16 |
Correct |
132 ms |
79260 KB |
Output is correct |
| 17 |
Correct |
344 ms |
79260 KB |
Output is correct |
| 18 |
Correct |
326 ms |
79304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
351 ms |
79304 KB |
Output is correct |
| 2 |
Correct |
414 ms |
79304 KB |
Output is correct |
| 3 |
Correct |
440 ms |
79332 KB |
Output is correct |
| 4 |
Incorrect |
245 ms |
79332 KB |
Output isn't correct |
| 5 |
Incorrect |
170 ms |
79532 KB |
Output isn't correct |
| 6 |
Correct |
350 ms |
79532 KB |
Output is correct |
| 7 |
Correct |
311 ms |
79532 KB |
Output is correct |
| 8 |
Correct |
331 ms |
79532 KB |
Output is correct |
| 9 |
Correct |
327 ms |
79532 KB |
Output is correct |
| 10 |
Correct |
268 ms |
79532 KB |
Output is correct |
| 11 |
Incorrect |
235 ms |
79532 KB |
Output isn't correct |
| 12 |
Correct |
300 ms |
79532 KB |
Output is correct |
| 13 |
Correct |
393 ms |
79532 KB |
Output is correct |
| 14 |
Correct |
232 ms |
79532 KB |
Output is correct |
| 15 |
Incorrect |
327 ms |
79532 KB |
Output isn't correct |
| 16 |
Correct |
361 ms |
79532 KB |
Output is correct |
| 17 |
Correct |
312 ms |
79532 KB |
Output is correct |
| 18 |
Correct |
420 ms |
79532 KB |
Output is correct |
| 19 |
Incorrect |
128 ms |
79532 KB |
Output isn't correct |
| 20 |
Correct |
393 ms |
79532 KB |
Output is correct |
| 21 |
Incorrect |
211 ms |
79676 KB |
Output isn't correct |
| 22 |
Correct |
350 ms |
79676 KB |
Output is correct |
| 23 |
Correct |
160 ms |
79676 KB |
Output is correct |
| 24 |
Correct |
131 ms |
79676 KB |
Output is correct |
| 25 |
Correct |
240 ms |
79676 KB |
Output is correct |
| 26 |
Incorrect |
233 ms |
79676 KB |
Output isn't correct |
| 27 |
Correct |
394 ms |
79676 KB |
Output is correct |
| 28 |
Incorrect |
129 ms |
79676 KB |
Output isn't correct |
| 29 |
Correct |
348 ms |
79676 KB |
Output is correct |
| 30 |
Correct |
304 ms |
79676 KB |
Output is correct |
| 31 |
Correct |
150 ms |
79676 KB |
Output is correct |
| 32 |
Incorrect |
185 ms |
79676 KB |
Output isn't correct |
| 33 |
Incorrect |
114 ms |
79676 KB |
Output isn't correct |
| 34 |
Correct |
248 ms |
79676 KB |
Output is correct |
| 35 |
Incorrect |
138 ms |
79676 KB |
Output isn't correct |
| 36 |
Correct |
412 ms |
79676 KB |
Output is correct |
| 37 |
Incorrect |
153 ms |
79676 KB |
Output isn't correct |
| 38 |
Correct |
277 ms |
79676 KB |
Output is correct |
| 39 |
Correct |
143 ms |
79676 KB |
Output is correct |
| 40 |
Correct |
240 ms |
79676 KB |
Output is correct |
| 41 |
Correct |
225 ms |
79676 KB |
Output is correct |
| 42 |
Correct |
393 ms |
79676 KB |
Output is correct |
