Submission #155766

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
155766	2019-09-30T13:05:28 Z	shuvi_dola	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	438 ms	79340 KB

brunhilda

#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 4;
const int N = 1e7 + 3;
const int inf = 1e9;
int p[M], dp[N], d[N];
int m, q;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> m >> q;
	for(int i = 1; i <= m; i++)
	{
		cin >> p[i];
	}

	for(int i = 1; i <= m; i++)
	{
		int j = p[i];
		while(j < N)
		{
			d[j] = max(d[j], p[i]);
			j += p[i];
			
		}
	}
	d[0] = p[m];
	int j = 0;
	for(int i = 1; i < N; i++)
	{
		while(j + d[j] - 1 < i)
		{
			j++;
		}
		// if(i <= 5)
			// cout << i << ' ' << j << '\n';
		if(j >= i)
			dp[i] = inf;
		dp[i] = dp[j] + 1;

	}
	while(q--)
	{
		int x;
		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	129 ms	78580 KB	Output is correct
2	Correct	156 ms	78676 KB	Output is correct
3	Correct	132 ms	78708 KB	Output is correct
4	Correct	113 ms	78840 KB	Output is correct
5	Correct	138 ms	78556 KB	Output is correct
6	Correct	129 ms	78560 KB	Output is correct
7	Correct	132 ms	78700 KB	Output is correct
8	Correct	136 ms	78632 KB	Output is correct
9	Correct	162 ms	78572 KB	Output is correct
10	Correct	176 ms	78588 KB	Output is correct
11	Correct	171 ms	78712 KB	Output is correct
12	Correct	111 ms	78584 KB	Output is correct
13	Correct	258 ms	78716 KB	Output is correct
14	Correct	262 ms	78584 KB	Output is correct
15	Correct	144 ms	78712 KB	Output is correct
16	Correct	131 ms	78632 KB	Output is correct
17	Correct	134 ms	78812 KB	Output is correct
18	Correct	121 ms	78648 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	78712 KB	Output is correct
2	Correct	147 ms	79068 KB	Output is correct
3	Correct	323 ms	78928 KB	Output is correct
4	Correct	151 ms	78624 KB	Output is correct
5	Correct	234 ms	78900 KB	Output is correct
6	Correct	145 ms	78676 KB	Output is correct
7	Correct	128 ms	78620 KB	Output is correct
8	Correct	157 ms	78576 KB	Output is correct
9	Correct	278 ms	78968 KB	Output is correct
10	Correct	325 ms	78968 KB	Output is correct
11	Correct	306 ms	78816 KB	Output is correct
12	Correct	185 ms	78704 KB	Output is correct
13	Correct	117 ms	78584 KB	Output is correct
14	Correct	149 ms	78712 KB	Output is correct
15	Correct	258 ms	78812 KB	Output is correct
16	Correct	156 ms	78968 KB	Output is correct
17	Correct	280 ms	78752 KB	Output is correct
18	Correct	270 ms	78984 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	313 ms	78868 KB	Output is correct
2	Correct	392 ms	78972 KB	Output is correct
3	Correct	329 ms	79024 KB	Output is correct
4	Correct	231 ms	78932 KB	Output is correct
5	Correct	167 ms	79224 KB	Output is correct
6	Correct	299 ms	78968 KB	Output is correct
7	Correct	244 ms	79212 KB	Output is correct
8	Correct	271 ms	78936 KB	Output is correct
9	Correct	279 ms	78940 KB	Output is correct
10	Correct	221 ms	78712 KB	Output is correct
11	Correct	187 ms	78716 KB	Output is correct
12	Correct	252 ms	78844 KB	Output is correct
13	Correct	363 ms	78968 KB	Output is correct
14	Correct	203 ms	79224 KB	Output is correct
15	Correct	292 ms	78744 KB	Output is correct
16	Correct	360 ms	78716 KB	Output is correct
17	Correct	261 ms	78880 KB	Output is correct
18	Correct	319 ms	78968 KB	Output is correct
19	Correct	128 ms	78712 KB	Output is correct
20	Correct	355 ms	78976 KB	Output is correct
21	Correct	300 ms	79340 KB	Output is correct
22	Correct	362 ms	79336 KB	Output is correct
23	Correct	193 ms	79068 KB	Output is correct
24	Correct	158 ms	78996 KB	Output is correct
25	Correct	298 ms	78968 KB	Output is correct
26	Correct	257 ms	79096 KB	Output is correct
27	Correct	438 ms	79196 KB	Output is correct
28	Correct	160 ms	78976 KB	Output is correct
29	Correct	386 ms	79268 KB	Output is correct
30	Correct	353 ms	79224 KB	Output is correct
31	Correct	173 ms	78840 KB	Output is correct
32	Correct	192 ms	78884 KB	Output is correct
33	Correct	136 ms	78968 KB	Output is correct
34	Correct	255 ms	79164 KB	Output is correct
35	Correct	157 ms	79012 KB	Output is correct
36	Correct	344 ms	79228 KB	Output is correct
37	Correct	173 ms	79224 KB	Output is correct
38	Correct	278 ms	78948 KB	Output is correct
39	Correct	161 ms	78992 KB	Output is correct
40	Correct	264 ms	79036 KB	Output is correct
41	Correct	235 ms	79100 KB	Output is correct
42	Correct	353 ms	79096 KB	Output is correct