답안 #535242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535242	2022-03-09T18:07:38 Z	MKutayBozkurt	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	560 ms	157508 KB

brunhilda

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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