답안 #522430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522430	2022-02-05T02:44:42 Z	Hamed5001	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	238 ms	79172 KB

brunhilda

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

const int mxN = 1e7+1;
int dp[mxN], dp2[mxN];

void solve() {
    int M, Q;
    cin >> M >> Q;
    vector<int> primes(M);
    for (auto &a : primes) cin >> a;
    
    for (auto p : primes) {
        for (int i = p; i <= mxN; i += p) {
            dp2[i - 1] = max(dp2[i - 1], p - 1);
        }
        dp2[mxN - 1] = max(dp2[mxN - 1], (mxN - 1) % p);
    }
    for (int i = mxN - 2; i >= 0; --i) {
        dp2[i] = max(dp2[i], dp2[i + 1] - 1);
    }
    
    dp[0] = 0;
    for (int i = 1; i < mxN; ++i) {
        dp[i] = 1e9;
        dp[i] = dp[i - dp2[i]] + 1;
    }
    
    while(Q--) {
        int n;
        cin >> n;
        int ans = dp[n];
        if (ans >= 1e9) cout << "oo\n";
        else cout << ans << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	61 ms	78460 KB	Output is correct
2	Correct	80 ms	78488 KB	Output is correct
3	Correct	72 ms	78452 KB	Output is correct
4	Correct	68 ms	78484 KB	Output is correct
5	Correct	70 ms	78472 KB	Output is correct
6	Correct	62 ms	78524 KB	Output is correct
7	Correct	72 ms	78476 KB	Output is correct
8	Correct	75 ms	78452 KB	Output is correct
9	Correct	95 ms	78468 KB	Output is correct
10	Correct	116 ms	78480 KB	Output is correct
11	Correct	97 ms	78476 KB	Output is correct
12	Correct	63 ms	78468 KB	Output is correct
13	Correct	174 ms	78532 KB	Output is correct
14	Correct	172 ms	78480 KB	Output is correct
15	Correct	98 ms	78548 KB	Output is correct
16	Correct	82 ms	78560 KB	Output is correct
17	Correct	82 ms	78604 KB	Output is correct
18	Correct	64 ms	78572 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	74 ms	78580 KB	Output is correct
2	Correct	96 ms	78916 KB	Output is correct
3	Correct	211 ms	78764 KB	Output is correct
4	Correct	90 ms	78576 KB	Output is correct
5	Correct	148 ms	78736 KB	Output is correct
6	Correct	81 ms	78580 KB	Output is correct
7	Correct	78 ms	78580 KB	Output is correct
8	Correct	90 ms	78476 KB	Output is correct
9	Correct	169 ms	78772 KB	Output is correct
10	Correct	212 ms	78764 KB	Output is correct
11	Correct	205 ms	78656 KB	Output is correct
12	Correct	116 ms	78468 KB	Output is correct
13	Correct	68 ms	78500 KB	Output is correct
14	Correct	102 ms	78492 KB	Output is correct
15	Correct	179 ms	78652 KB	Output is correct
16	Correct	84 ms	78848 KB	Output is correct
17	Correct	200 ms	78560 KB	Output is correct
18	Correct	177 ms	78956 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	187 ms	78808 KB	Output is correct
2	Correct	222 ms	78820 KB	Output is correct
3	Correct	217 ms	78940 KB	Output is correct
4	Correct	147 ms	78808 KB	Output is correct
5	Correct	104 ms	79044 KB	Output is correct
6	Correct	193 ms	78816 KB	Output is correct
7	Correct	158 ms	79044 KB	Output is correct
8	Correct	196 ms	78812 KB	Output is correct
9	Correct	177 ms	78820 KB	Output is correct
10	Correct	138 ms	78532 KB	Output is correct
11	Correct	121 ms	78660 KB	Output is correct
12	Correct	167 ms	78600 KB	Output is correct
13	Correct	208 ms	78856 KB	Output is correct
14	Correct	135 ms	79116 KB	Output is correct
15	Correct	171 ms	78624 KB	Output is correct
16	Correct	198 ms	78628 KB	Output is correct
17	Correct	164 ms	78668 KB	Output is correct
18	Correct	215 ms	78788 KB	Output is correct
19	Correct	76 ms	78612 KB	Output is correct
20	Correct	220 ms	78916 KB	Output is correct
21	Correct	157 ms	79172 KB	Output is correct
22	Correct	229 ms	79088 KB	Output is correct
23	Correct	109 ms	78916 KB	Output is correct
24	Correct	95 ms	78776 KB	Output is correct
25	Correct	154 ms	78868 KB	Output is correct
26	Correct	141 ms	78788 KB	Output is correct
27	Correct	238 ms	79000 KB	Output is correct
28	Correct	89 ms	78788 KB	Output is correct
29	Correct	217 ms	79140 KB	Output is correct
30	Correct	195 ms	79016 KB	Output is correct
31	Correct	105 ms	78788 KB	Output is correct
32	Correct	123 ms	78872 KB	Output is correct
33	Correct	87 ms	78812 KB	Output is correct
34	Correct	158 ms	79044 KB	Output is correct
35	Correct	95 ms	78788 KB	Output is correct
36	Correct	235 ms	79152 KB	Output is correct
37	Correct	105 ms	79172 KB	Output is correct
38	Correct	185 ms	78812 KB	Output is correct
39	Correct	101 ms	78788 KB	Output is correct
40	Correct	167 ms	78768 KB	Output is correct
41	Correct	142 ms	79004 KB	Output is correct
42	Correct	200 ms	78876 KB	Output is correct