oj.uz

Submission #535242

# Submission time Handle Problem Language Result Execution time Memory
535242 2022-03-09T18:07:38 Z MKutayBozkurt Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 560 ms 157508 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int mx = 2e7 + 5;
int bst[mx] = {}, dp[mx];
 
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); 
  int n, q; cin >> n >> q; 
  int A[n];
  for (int i = 0; i < n; i++) {
    cin >> A[i];
    for (int mul = A[i] - 1; mul < mx; mul += A[i]) bst[mul] = max(bst[mul], A[i] - 1);
  }
  for (int i = mx - 2; i; i--) bst[i] = max(bst[i], bst[i + 1] - 1);

  fill(dp, dp + mx, 1e9); dp[0] = 0; 
  for (int i = 1; i < mx; i++) dp[i] = dp[i - bst[i]] + 1;
  
  while (q--) {
    int x; cin >> x;
    cout << (dp[x] >= 1e9 ? "oo" : to_string(dp[x])) << '\n';
  }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 156740 KB Output is correct
2 Correct 223 ms 156852 KB Output is correct
3 Correct 208 ms 156780 KB Output is correct
4 Correct 190 ms 156868 KB Output is correct
5 Correct 216 ms 156788 KB Output is correct
6 Correct 187 ms 156784 KB Output is correct
7 Correct 200 ms 156788 KB Output is correct
8 Correct 204 ms 156784 KB Output is correct
9 Correct 249 ms 156780 KB Output is correct
10 Correct 282 ms 156868 KB Output is correct
11 Correct 267 ms 156788 KB Output is correct
12 Correct 185 ms 156756 KB Output is correct
13 Correct 437 ms 156928 KB Output is correct
14 Correct 409 ms 156868 KB Output is correct
15 Correct 255 ms 156840 KB Output is correct
16 Correct 247 ms 156896 KB Output is correct
17 Correct 220 ms 156788 KB Output is correct
18 Correct 179 ms 156788 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 156896 KB Output is correct
2 Correct 271 ms 157140 KB Output is correct
3 Correct 490 ms 157124 KB Output is correct
4 Correct 243 ms 156756 KB Output is correct
5 Correct 359 ms 157020 KB Output is correct
6 Correct 214 ms 156788 KB Output is correct
7 Correct 235 ms 156832 KB Output is correct
8 Correct 267 ms 156740 KB Output is correct
9 Correct 449 ms 157040 KB Output is correct
10 Correct 535 ms 157124 KB Output is correct
11 Correct 509 ms 156940 KB Output is correct
12 Correct 304 ms 156868 KB Output is correct
13 Correct 207 ms 156844 KB Output is correct
14 Correct 241 ms 156796 KB Output is correct
15 Correct 450 ms 156948 KB Output is correct
16 Correct 235 ms 157144 KB Output is correct
17 Correct 455 ms 156800 KB Output is correct
18 Correct 408 ms 157176 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 157108 KB Output is correct
2 Correct 554 ms 157176 KB Output is correct
3 Correct 518 ms 157144 KB Output is correct
4 Correct 335 ms 157104 KB Output is correct
5 Correct 252 ms 157428 KB Output is correct
6 Correct 435 ms 157068 KB Output is correct
7 Correct 410 ms 157244 KB Output is correct
8 Correct 430 ms 157112 KB Output is correct
9 Correct 419 ms 157108 KB Output is correct
10 Correct 357 ms 156808 KB Output is correct
11 Correct 298 ms 156920 KB Output is correct
12 Correct 408 ms 156864 KB Output is correct
13 Correct 476 ms 157284 KB Output is correct
14 Correct 316 ms 157380 KB Output is correct
15 Correct 430 ms 156996 KB Output is correct
16 Correct 453 ms 156916 KB Output is correct
17 Correct 417 ms 156948 KB Output is correct
18 Correct 547 ms 157048 KB Output is correct
19 Correct 207 ms 156996 KB Output is correct
20 Correct 510 ms 157096 KB Output is correct
21 Correct 359 ms 157432 KB Output is correct
22 Correct 560 ms 157508 KB Output is correct
23 Correct 269 ms 157152 KB Output is correct
24 Correct 238 ms 157212 KB Output is correct
25 Correct 382 ms 157176 KB Output is correct
26 Correct 326 ms 157120 KB Output is correct
27 Correct 556 ms 157300 KB Output is correct
28 Correct 244 ms 157044 KB Output is correct
29 Correct 508 ms 157448 KB Output is correct
30 Correct 464 ms 157316 KB Output is correct
31 Correct 285 ms 157060 KB Output is correct
32 Correct 277 ms 157048 KB Output is correct
33 Correct 229 ms 157084 KB Output is correct
34 Correct 380 ms 157240 KB Output is correct
35 Correct 269 ms 157036 KB Output is correct
36 Correct 505 ms 157392 KB Output is correct
37 Correct 293 ms 157336 KB Output is correct
38 Correct 439 ms 157200 KB Output is correct
39 Correct 240 ms 157136 KB Output is correct
40 Correct 379 ms 157072 KB Output is correct
41 Correct 346 ms 157280 KB Output is correct
42 Correct 470 ms 157292 KB Output is correct