oj.uz

Submission #535231

# Submission time Handle Problem Language Result Execution time Memory
535231 2022-03-09T17:53:15 Z MKutayBozkurt Brunhilda’s Birthday (BOI13_brunhilda) C++14
77.4603 / 100
 333 ms 158276 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, q; cin >> n >> q;
  vector<int> a(n), d((int) 1e7 + 7), dp((int) 1e7 + 7, 1e9);
  for (int &x : a) {
    cin >> x;
    for (int i = x - 1; i <= 1e7; i += x) {
      d[i] = x - 1;
    }
  }

  for (int i = 1e7; i > 0; i--) d[i] = max(d[i], d[i + 1] - 1);

  dp[0] = 0;
  for (int i = 1; i <= 1e7; i++) {
    dp[i] = dp[i - d[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 122 ms 156872 KB Output is correct
2 Correct 155 ms 156872 KB Output is correct
3 Correct 165 ms 156832 KB Output is correct
4 Correct 117 ms 156920 KB Output is correct
5 Correct 141 ms 156848 KB Output is correct
6 Correct 127 ms 156764 KB Output is correct
7 Correct 155 ms 156740 KB Output is correct
8 Correct 174 ms 156740 KB Output is correct
9 Correct 162 ms 156816 KB Output is correct
10 Correct 195 ms 156996 KB Output is correct
11 Correct 174 ms 156820 KB Output is correct
12 Correct 115 ms 156744 KB Output is correct
13 Correct 242 ms 156784 KB Output is correct
14 Correct 244 ms 156928 KB Output is correct
15 Correct 164 ms 156864 KB Output is correct
16 Correct 167 ms 156812 KB Output is correct
17 Correct 133 ms 156912 KB Output is correct
18 Correct 125 ms 156912 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 156984 KB Output is correct
2 Correct 144 ms 158276 KB Output is correct
3 Correct 295 ms 157844 KB Output is correct
4 Correct 157 ms 157004 KB Output is correct
5 Correct 216 ms 157508 KB Output is correct
6 Correct 145 ms 156856 KB Output is correct
7 Correct 128 ms 156992 KB Output is correct
8 Correct 165 ms 156888 KB Output is correct
9 Correct 235 ms 157604 KB Output is correct
10 Correct 297 ms 157512 KB Output is correct
11 Incorrect 279 ms 157124 KB Output isn't correct
12 Correct 188 ms 156876 KB Output is correct
13 Correct 170 ms 156784 KB Output is correct
14 Correct 154 ms 156872 KB Output is correct
15 Correct 251 ms 157124 KB Output is correct
16 Correct 179 ms 157580 KB Output is correct
17 Correct 264 ms 157004 KB Output is correct
18 Correct 241 ms 157732 KB Output is correct

Subtask #3
38.5714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 157288 KB Output is correct
2 Correct 320 ms 157276 KB Output is correct
3 Correct 305 ms 157388 KB Output is correct
4 Incorrect 243 ms 157132 KB Output isn't correct
5 Incorrect 190 ms 157784 KB Output isn't correct
6 Correct 280 ms 157184 KB Output is correct
7 Correct 245 ms 157732 KB Output is correct
8 Correct 268 ms 157276 KB Output is correct
9 Correct 271 ms 157276 KB Output is correct
10 Correct 203 ms 156912 KB Output is correct
11 Incorrect 216 ms 156864 KB Output isn't correct
12 Correct 248 ms 156940 KB Output is correct
13 Correct 275 ms 157392 KB Output is correct
14 Correct 211 ms 157476 KB Output is correct
15 Incorrect 265 ms 156904 KB Output isn't correct
16 Correct 280 ms 156996 KB Output is correct
17 Correct 254 ms 157224 KB Output is correct
18 Correct 296 ms 157364 KB Output is correct
19 Incorrect 164 ms 156868 KB Output isn't correct
20 Correct 304 ms 157484 KB Output is correct
21 Incorrect 221 ms 157380 KB Output isn't correct
22 Correct 333 ms 157784 KB Output is correct
23 Correct 168 ms 157328 KB Output is correct
24 Correct 156 ms 157112 KB Output is correct
25 Incorrect 241 ms 157120 KB Output isn't correct
26 Incorrect 233 ms 157140 KB Output isn't correct
27 Correct 332 ms 157656 KB Output is correct
28 Incorrect 155 ms 157124 KB Output isn't correct
29 Correct 287 ms 157780 KB Output is correct
30 Correct 263 ms 157540 KB Output is correct
31 Correct 170 ms 157052 KB Output is correct
32 Incorrect 186 ms 157124 KB Output isn't correct
33 Incorrect 149 ms 157064 KB Output isn't correct
34 Correct 256 ms 157652 KB Output is correct
35 Incorrect 154 ms 157176 KB Output isn't correct
36 Correct 314 ms 157716 KB Output is correct
37 Incorrect 186 ms 157992 KB Output isn't correct
38 Correct 269 ms 157188 KB Output is correct
39 Incorrect 167 ms 157124 KB Output isn't correct
40 Correct 248 ms 157256 KB Output is correct
41 Correct 216 ms 157652 KB Output is correct
42 Incorrect 285 ms 157248 KB Output isn't correct