답안 #494644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494644	2021-12-16T00:41:37 Z	SirCovidThe19th	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	558 ms	157436 KB

brunhilda

#include <bits/stdc++.h>
using namespace std;

const int mx = 2e7 + 5;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n, q; cin >> n >> q; 
    int A[n], bst[mx] = {}, dp[mx];
    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	191 ms	156840 KB	Output is correct
2	Correct	221 ms	156744 KB	Output is correct
3	Correct	198 ms	156748 KB	Output is correct
4	Correct	189 ms	156808 KB	Output is correct
5	Correct	207 ms	156840 KB	Output is correct
6	Correct	196 ms	156852 KB	Output is correct
7	Correct	209 ms	156740 KB	Output is correct
8	Correct	215 ms	156824 KB	Output is correct
9	Correct	239 ms	156760 KB	Output is correct
10	Correct	268 ms	156844 KB	Output is correct
11	Correct	260 ms	156844 KB	Output is correct
12	Correct	177 ms	156928 KB	Output is correct
13	Correct	406 ms	156880 KB	Output is correct
14	Correct	443 ms	156868 KB	Output is correct
15	Correct	251 ms	156840 KB	Output is correct
16	Correct	220 ms	156728 KB	Output is correct
17	Correct	228 ms	156796 KB	Output is correct
18	Correct	194 ms	156840 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	201 ms	156804 KB	Output is correct
2	Correct	263 ms	157200 KB	Output is correct
3	Correct	492 ms	156996 KB	Output is correct
4	Correct	244 ms	156868 KB	Output is correct
5	Correct	359 ms	157120 KB	Output is correct
6	Correct	223 ms	156844 KB	Output is correct
7	Correct	208 ms	156904 KB	Output is correct
8	Correct	242 ms	156748 KB	Output is correct
9	Correct	422 ms	157120 KB	Output is correct
10	Correct	524 ms	157172 KB	Output is correct
11	Correct	475 ms	156996 KB	Output is correct
12	Correct	289 ms	156740 KB	Output is correct
13	Correct	195 ms	156868 KB	Output is correct
14	Correct	250 ms	156868 KB	Output is correct
15	Correct	406 ms	157004 KB	Output is correct
16	Correct	231 ms	157204 KB	Output is correct
17	Correct	435 ms	156764 KB	Output is correct
18	Correct	446 ms	157236 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	455 ms	157044 KB	Output is correct
2	Correct	501 ms	156992 KB	Output is correct
3	Correct	512 ms	157192 KB	Output is correct
4	Correct	336 ms	157116 KB	Output is correct
5	Correct	281 ms	157364 KB	Output is correct
6	Correct	427 ms	157048 KB	Output is correct
7	Correct	404 ms	157240 KB	Output is correct
8	Correct	409 ms	157120 KB	Output is correct
9	Correct	415 ms	157036 KB	Output is correct
10	Correct	349 ms	156876 KB	Output is correct
11	Correct	325 ms	156940 KB	Output is correct
12	Correct	389 ms	156868 KB	Output is correct
13	Correct	462 ms	157140 KB	Output is correct
14	Correct	332 ms	157356 KB	Output is correct
15	Correct	441 ms	156940 KB	Output is correct
16	Correct	447 ms	156880 KB	Output is correct
17	Correct	413 ms	156996 KB	Output is correct
18	Correct	513 ms	157044 KB	Output is correct
19	Correct	207 ms	156868 KB	Output is correct
20	Correct	503 ms	157256 KB	Output is correct
21	Correct	335 ms	157436 KB	Output is correct
22	Correct	533 ms	157420 KB	Output is correct
23	Correct	260 ms	157088 KB	Output is correct
24	Correct	232 ms	157028 KB	Output is correct
25	Correct	347 ms	157120 KB	Output is correct
26	Correct	316 ms	157116 KB	Output is correct
27	Correct	558 ms	157360 KB	Output is correct
28	Correct	224 ms	157140 KB	Output is correct
29	Correct	538 ms	157356 KB	Output is correct
30	Correct	468 ms	157252 KB	Output is correct
31	Correct	254 ms	157164 KB	Output is correct
32	Correct	273 ms	157108 KB	Output is correct
33	Correct	211 ms	157184 KB	Output is correct
34	Correct	377 ms	157224 KB	Output is correct
35	Correct	246 ms	157084 KB	Output is correct
36	Correct	498 ms	157344 KB	Output is correct
37	Correct	258 ms	157344 KB	Output is correct
38	Correct	423 ms	157128 KB	Output is correct
39	Correct	237 ms	157116 KB	Output is correct
40	Correct	363 ms	157240 KB	Output is correct
41	Correct	343 ms	157232 KB	Output is correct
42	Correct	456 ms	157272 KB	Output is correct