Submission #155752

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
155752	2019-09-30T09:02:56 Z	souhhcong	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	446 ms	87160 KB

brunhilda

#include <iostream>
#include <string.h>
using namespace std;

const int N = 1e5+5, MAXN = 1e7+1e6, INF = 1e9+9;
int n, q, x, p[N], dp[MAXN], mx[MAXN];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++)
    {
        cin >> p[i];
        for (int j = p[i]-1; j < MAXN; j += p[i])
        {
            mx[j] = max(mx[j], p[i]-1);
        }
    }
	for (int i = MAXN - 2; i >= 0; i--)
		mx[i] = max(mx[i], mx[i+1]-1);
    for (int i = 1; i < MAXN; i++)
    {
        if (mx[i] > 0)
            dp[i] = 1 + dp[i-mx[i]];
        else
            dp[i] = INF;
    }
    while(q--)
    {
        cin >> x;
        if (dp[x] >= INF) cout << "oo\n";
        else cout << dp[x] << '\n';
    }
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	151 ms	86392 KB	Output is correct
2	Correct	174 ms	86392 KB	Output is correct
3	Correct	163 ms	86520 KB	Output is correct
4	Correct	150 ms	86392 KB	Output is correct
5	Correct	165 ms	86576 KB	Output is correct
6	Correct	161 ms	86460 KB	Output is correct
7	Correct	165 ms	86488 KB	Output is correct
8	Correct	169 ms	86376 KB	Output is correct
9	Correct	210 ms	86648 KB	Output is correct
10	Correct	220 ms	86520 KB	Output is correct
11	Correct	209 ms	86520 KB	Output is correct
12	Correct	148 ms	86392 KB	Output is correct
13	Correct	352 ms	86520 KB	Output is correct
14	Correct	355 ms	86456 KB	Output is correct
15	Correct	195 ms	86520 KB	Output is correct
16	Correct	178 ms	86520 KB	Output is correct
17	Correct	177 ms	86548 KB	Output is correct
18	Correct	150 ms	86428 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	190 ms	86568 KB	Output is correct
2	Correct	221 ms	86812 KB	Output is correct
3	Correct	416 ms	86712 KB	Output is correct
4	Correct	202 ms	86568 KB	Output is correct
5	Correct	294 ms	86748 KB	Output is correct
6	Correct	175 ms	86392 KB	Output is correct
7	Correct	182 ms	86416 KB	Output is correct
8	Correct	190 ms	86392 KB	Output is correct
9	Correct	341 ms	86684 KB	Output is correct
10	Correct	394 ms	86648 KB	Output is correct
11	Correct	381 ms	86584 KB	Output is correct
12	Correct	241 ms	86392 KB	Output is correct
13	Correct	155 ms	86396 KB	Output is correct
14	Correct	193 ms	86520 KB	Output is correct
15	Correct	336 ms	86648 KB	Output is correct
16	Correct	188 ms	86828 KB	Output is correct
17	Correct	396 ms	86504 KB	Output is correct
18	Correct	338 ms	86960 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	369 ms	86712 KB	Output is correct
2	Correct	396 ms	86808 KB	Output is correct
3	Correct	400 ms	86904 KB	Output is correct
4	Correct	271 ms	86776 KB	Output is correct
5	Correct	239 ms	87032 KB	Output is correct
6	Correct	384 ms	86776 KB	Output is correct
7	Correct	307 ms	87160 KB	Output is correct
8	Correct	340 ms	86776 KB	Output is correct
9	Correct	335 ms	86776 KB	Output is correct
10	Correct	278 ms	86520 KB	Output is correct
11	Correct	244 ms	86648 KB	Output is correct
12	Correct	309 ms	86520 KB	Output is correct
13	Correct	386 ms	86892 KB	Output is correct
14	Correct	245 ms	87032 KB	Output is correct
15	Correct	392 ms	86644 KB	Output is correct
16	Correct	413 ms	86620 KB	Output is correct
17	Correct	369 ms	86648 KB	Output is correct
18	Correct	431 ms	86876 KB	Output is correct
19	Correct	169 ms	86472 KB	Output is correct
20	Correct	401 ms	86780 KB	Output is correct
21	Correct	313 ms	87032 KB	Output is correct
22	Correct	434 ms	87100 KB	Output is correct
23	Correct	253 ms	86904 KB	Output is correct
24	Correct	190 ms	86776 KB	Output is correct
25	Correct	287 ms	86788 KB	Output is correct
26	Correct	283 ms	86648 KB	Output is correct
27	Correct	446 ms	86920 KB	Output is correct
28	Correct	187 ms	86780 KB	Output is correct
29	Correct	392 ms	86984 KB	Output is correct
30	Correct	366 ms	86960 KB	Output is correct
31	Correct	248 ms	86780 KB	Output is correct
32	Correct	234 ms	86732 KB	Output is correct
33	Correct	180 ms	86852 KB	Output is correct
34	Correct	364 ms	87032 KB	Output is correct
35	Correct	195 ms	86776 KB	Output is correct
36	Correct	412 ms	86980 KB	Output is correct
37	Correct	228 ms	87160 KB	Output is correct
38	Correct	377 ms	86744 KB	Output is correct
39	Correct	219 ms	86720 KB	Output is correct
40	Correct	296 ms	86800 KB	Output is correct
41	Correct	277 ms	86968 KB	Output is correct
42	Correct	361 ms	87032 KB	Output is correct