Submission #155734

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
155734	2019-09-30T07:17:55 Z	shuvi_dola	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	17.7778 / 100	1000 ms	262148 KB

brunhilda

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;;
const int lim = 1e7 + 3;
const int inf = 1e9 + 9;
int p[N], m, q;
int dp[lim];
string s;
int dfs(int u)
{
	if(dp[u] != inf)
		return dp[u];

	if(u == 0)
		return 0;
	int cnt = 0;
	for(int i = 1; i <= m; i++)
	{
		
		if(u % p[i] == 0 && u != 0)
		{
			cnt ++;
			continue;
		}

		dp[u] = min(dp[u], dfs(u - u % p[i]) + 1);
	}
	if(cnt == m)
	{
		dp[u] = inf - 1;
		return inf - 1;
	}

	return dp[u];
}

int main()
{
	for(int i = 1; i < lim; i++)
	{
		dp[i] = inf;
	}
	cin >> m >> q;
	for(int i = 1; i <= m; i++)
	{
		cin >> p[i];
	}
	sort(p + 1, p + 1 + m);
	for(int i = 1; i <= q; i++)
	{
		int n;
		cin >> n;
		dfs(n);
		if(dp[n] == inf - 1)
			cout << "oo\n";
		else
			cout << dp[n] << '\n';
	}
}

Subtask #1

17.7777777778 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1075 ms	39544 KB	Time limit exceeded
2	Correct	38 ms	39416 KB	Output is correct
3	Correct	35 ms	39544 KB	Output is correct
4	Correct	70 ms	39496 KB	Output is correct
5	Correct	36 ms	39388 KB	Output is correct
6	Execution timed out	1086 ms	39416 KB	Time limit exceeded
7	Correct	35 ms	39544 KB	Output is correct
8	Correct	35 ms	39544 KB	Output is correct
9	Correct	35 ms	39416 KB	Output is correct
10	Correct	39 ms	39544 KB	Output is correct
11	Correct	40 ms	39544 KB	Output is correct
12	Correct	35 ms	39416 KB	Output is correct
13	Correct	101 ms	39708 KB	Output is correct
14	Correct	122 ms	39528 KB	Output is correct
15	Correct	44 ms	39544 KB	Output is correct
16	Correct	44 ms	39416 KB	Output is correct
17	Correct	70 ms	39468 KB	Output is correct
18	Correct	71 ms	39416 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1065 ms	43512 KB	Time limit exceeded
2	Execution timed out	1079 ms	59480 KB	Time limit exceeded
3	Execution timed out	1060 ms	163424 KB	Time limit exceeded
4	Execution timed out	1079 ms	71332 KB	Time limit exceeded
5	Execution timed out	1077 ms	76920 KB	Time limit exceeded
6	Execution timed out	1058 ms	51192 KB	Time limit exceeded
7	Execution timed out	1050 ms	43608 KB	Time limit exceeded
8	Execution timed out	1072 ms	51832 KB	Time limit exceeded
9	Execution timed out	1079 ms	67064 KB	Time limit exceeded
10	Execution timed out	1078 ms	163280 KB	Time limit exceeded
11	Runtime error	305 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Execution timed out	1076 ms	114796 KB	Time limit exceeded
13	Execution timed out	1052 ms	73052 KB	Time limit exceeded
14	Execution timed out	1075 ms	71288 KB	Time limit exceeded
15	Execution timed out	1076 ms	104056 KB	Time limit exceeded
16	Execution timed out	1077 ms	59512 KB	Time limit exceeded
17	Runtime error	282 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Execution timed out	1081 ms	212548 KB	Time limit exceeded

Subtask #3

0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	325 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Execution timed out	1064 ms	52792 KB	Time limit exceeded
3	Execution timed out	1070 ms	223148 KB	Time limit exceeded
4	Execution timed out	1057 ms	148512 KB	Time limit exceeded
5	Execution timed out	1075 ms	40440 KB	Time limit exceeded
6	Execution timed out	1083 ms	207932 KB	Time limit exceeded
7	Execution timed out	1076 ms	74872 KB	Time limit exceeded
8	Runtime error	309 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Runtime error	315 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Execution timed out	1053 ms	47328 KB	Time limit exceeded
11	Execution timed out	1074 ms	84204 KB	Time limit exceeded
12	Execution timed out	1083 ms	168884 KB	Time limit exceeded
13	Execution timed out	1067 ms	126968 KB	Time limit exceeded
14	Execution timed out	1083 ms	195192 KB	Time limit exceeded
15	Runtime error	311 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Execution timed out	1096 ms	187000 KB	Time limit exceeded
17	Execution timed out	1079 ms	56236 KB	Time limit exceeded
18	Execution timed out	1089 ms	52856 KB	Time limit exceeded
19	Execution timed out	1079 ms	52744 KB	Time limit exceeded
20	Execution timed out	1107 ms	223224 KB	Time limit exceeded
21	Runtime error	282 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Execution timed out	1096 ms	226168 KB	Time limit exceeded
23	Execution timed out	1050 ms	40440 KB	Time limit exceeded
24	Execution timed out	1069 ms	48248 KB	Time limit exceeded
25	Execution timed out	1082 ms	45816 KB	Time limit exceeded
26	Execution timed out	1081 ms	148420 KB	Time limit exceeded
27	Execution timed out	1072 ms	223376 KB	Time limit exceeded
28	Execution timed out	1085 ms	87672 KB	Time limit exceeded
29	Execution timed out	1087 ms	92920 KB	Time limit exceeded
30	Execution timed out	1085 ms	68484 KB	Time limit exceeded
31	Execution timed out	1079 ms	74832 KB	Time limit exceeded
32	Execution timed out	1092 ms	77560 KB	Time limit exceeded
33	Execution timed out	1093 ms	48376 KB	Time limit exceeded
34	Execution timed out	1082 ms	74972 KB	Time limit exceeded
35	Execution timed out	1084 ms	54776 KB	Time limit exceeded
36	Execution timed out	1032 ms	70136 KB	Time limit exceeded
37	Execution timed out	1081 ms	40440 KB	Time limit exceeded
38	Execution timed out	1084 ms	207888 KB	Time limit exceeded
39	Execution timed out	1064 ms	47864 KB	Time limit exceeded
40	Execution timed out	1084 ms	102008 KB	Time limit exceeded
41	Execution timed out	1088 ms	93564 KB	Time limit exceeded
42	Runtime error	287 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)