Submission #155751

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
155751	2019-09-30T08:59:52 Z	souhhcong	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	97.7778 / 100	483 ms	87132 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

17.7777777778 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	150 ms	86424 KB	Output isn't correct
2	Correct	175 ms	86492 KB	Output is correct
3	Correct	163 ms	86520 KB	Output is correct
4	Correct	150 ms	86392 KB	Output is correct
5	Correct	164 ms	86492 KB	Output is correct
6	Incorrect	165 ms	86492 KB	Output isn't correct
7	Correct	180 ms	86392 KB	Output is correct
8	Correct	170 ms	86392 KB	Output is correct
9	Correct	190 ms	86436 KB	Output is correct
10	Correct	227 ms	86520 KB	Output is correct
11	Correct	198 ms	86524 KB	Output is correct
12	Correct	146 ms	86492 KB	Output is correct
13	Correct	320 ms	86492 KB	Output is correct
14	Correct	318 ms	86588 KB	Output is correct
15	Correct	183 ms	86520 KB	Output is correct
16	Correct	175 ms	86392 KB	Output is correct
17	Correct	179 ms	86520 KB	Output is correct
18	Correct	150 ms	86520 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	166 ms	86456 KB	Output is correct
2	Correct	188 ms	86740 KB	Output is correct
3	Correct	397 ms	86728 KB	Output is correct
4	Correct	189 ms	86500 KB	Output is correct
5	Correct	279 ms	86584 KB	Output is correct
6	Correct	172 ms	86392 KB	Output is correct
7	Correct	167 ms	86520 KB	Output is correct
8	Correct	191 ms	86540 KB	Output is correct
9	Correct	329 ms	86776 KB	Output is correct
10	Correct	384 ms	86820 KB	Output is correct
11	Correct	378 ms	86648 KB	Output is correct
12	Correct	244 ms	86392 KB	Output is correct
13	Correct	170 ms	86452 KB	Output is correct
14	Correct	196 ms	86488 KB	Output is correct
15	Correct	344 ms	86560 KB	Output is correct
16	Correct	209 ms	86776 KB	Output is correct
17	Correct	378 ms	86500 KB	Output is correct
18	Correct	346 ms	86876 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	343 ms	86776 KB	Output is correct
2	Correct	443 ms	86904 KB	Output is correct
3	Correct	482 ms	86840 KB	Output is correct
4	Correct	266 ms	86696 KB	Output is correct
5	Correct	225 ms	87032 KB	Output is correct
6	Correct	344 ms	86708 KB	Output is correct
7	Correct	299 ms	87048 KB	Output is correct
8	Correct	334 ms	86816 KB	Output is correct
9	Correct	367 ms	86744 KB	Output is correct
10	Correct	321 ms	86776 KB	Output is correct
11	Correct	348 ms	86520 KB	Output is correct
12	Correct	310 ms	86456 KB	Output is correct
13	Correct	374 ms	86856 KB	Output is correct
14	Correct	250 ms	87004 KB	Output is correct
15	Correct	392 ms	86776 KB	Output is correct
16	Correct	406 ms	86616 KB	Output is correct
17	Correct	386 ms	86768 KB	Output is correct
18	Correct	441 ms	86772 KB	Output is correct
19	Correct	170 ms	86648 KB	Output is correct
20	Correct	396 ms	86868 KB	Output is correct
21	Correct	271 ms	87132 KB	Output is correct
22	Correct	418 ms	86976 KB	Output is correct
23	Correct	246 ms	86952 KB	Output is correct
24	Correct	200 ms	86776 KB	Output is correct
25	Correct	300 ms	86948 KB	Output is correct
26	Correct	265 ms	86896 KB	Output is correct
27	Correct	483 ms	86964 KB	Output is correct
28	Correct	200 ms	86716 KB	Output is correct
29	Correct	394 ms	87052 KB	Output is correct
30	Correct	418 ms	87092 KB	Output is correct
31	Correct	211 ms	86812 KB	Output is correct
32	Correct	230 ms	86764 KB	Output is correct
33	Correct	181 ms	86776 KB	Output is correct
34	Correct	310 ms	87004 KB	Output is correct
35	Correct	194 ms	86776 KB	Output is correct
36	Correct	399 ms	87108 KB	Output is correct
37	Correct	234 ms	86952 KB	Output is correct
38	Correct	367 ms	86848 KB	Output is correct
39	Correct	234 ms	86904 KB	Output is correct
40	Correct	345 ms	86716 KB	Output is correct
41	Correct	278 ms	86904 KB	Output is correct
42	Correct	374 ms	86904 KB	Output is correct