Submission #155740

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

brunhilda

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
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()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	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	1082 ms	39416 KB	Time limit exceeded
2	Correct	35 ms	39416 KB	Output is correct
3	Correct	34 ms	39548 KB	Output is correct
4	Correct	40 ms	39544 KB	Output is correct
5	Correct	34 ms	39544 KB	Output is correct
6	Execution timed out	1068 ms	39544 KB	Time limit exceeded
7	Correct	33 ms	39544 KB	Output is correct
8	Correct	34 ms	39544 KB	Output is correct
9	Correct	34 ms	39516 KB	Output is correct
10	Correct	35 ms	39544 KB	Output is correct
11	Correct	35 ms	39672 KB	Output is correct
12	Correct	40 ms	39416 KB	Output is correct
13	Correct	89 ms	39672 KB	Output is correct
14	Correct	87 ms	39544 KB	Output is correct
15	Correct	35 ms	39552 KB	Output is correct
16	Correct	36 ms	39464 KB	Output is correct
17	Correct	44 ms	39544 KB	Output is correct
18	Correct	40 ms	39572 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1057 ms	43512 KB	Time limit exceeded
2	Execution timed out	1069 ms	59512 KB	Time limit exceeded
3	Execution timed out	1092 ms	163320 KB	Time limit exceeded
4	Execution timed out	1084 ms	71288 KB	Time limit exceeded
5	Execution timed out	1087 ms	76920 KB	Time limit exceeded
6	Execution timed out	1064 ms	51324 KB	Time limit exceeded
7	Execution timed out	1073 ms	43640 KB	Time limit exceeded
8	Execution timed out	1070 ms	51832 KB	Time limit exceeded
9	Execution timed out	1090 ms	67192 KB	Time limit exceeded
10	Execution timed out	1091 ms	163320 KB	Time limit exceeded
11	Runtime error	300 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Execution timed out	1096 ms	114856 KB	Time limit exceeded
13	Execution timed out	1087 ms	72952 KB	Time limit exceeded
14	Execution timed out	1084 ms	71288 KB	Time limit exceeded
15	Execution timed out	1089 ms	104056 KB	Time limit exceeded
16	Execution timed out	1079 ms	59512 KB	Time limit exceeded
17	Runtime error	281 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Execution timed out	1096 ms	212600 KB	Time limit exceeded

Subtask #3

0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	280 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Execution timed out	1077 ms	52856 KB	Time limit exceeded
3	Execution timed out	1077 ms	223184 KB	Time limit exceeded
4	Execution timed out	1098 ms	148344 KB	Time limit exceeded
5	Execution timed out	1084 ms	40568 KB	Time limit exceeded
6	Execution timed out	1091 ms	207992 KB	Time limit exceeded
7	Execution timed out	1090 ms	75000 KB	Time limit exceeded
8	Runtime error	296 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Runtime error	281 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Execution timed out	1078 ms	47352 KB	Time limit exceeded
11	Execution timed out	1064 ms	84236 KB	Time limit exceeded
12	Execution timed out	1077 ms	168988 KB	Time limit exceeded
13	Execution timed out	1086 ms	126972 KB	Time limit exceeded
14	Execution timed out	1089 ms	195064 KB	Time limit exceeded
15	Runtime error	317 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Execution timed out	1104 ms	187000 KB	Time limit exceeded
17	Execution timed out	1079 ms	56184 KB	Time limit exceeded
18	Execution timed out	1085 ms	52936 KB	Time limit exceeded
19	Execution timed out	1081 ms	52728 KB	Time limit exceeded
20	Execution timed out	1098 ms	223376 KB	Time limit exceeded
21	Runtime error	303 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Execution timed out	1086 ms	226184 KB	Time limit exceeded
23	Execution timed out	1090 ms	40568 KB	Time limit exceeded
24	Execution timed out	1079 ms	48376 KB	Time limit exceeded
25	Execution timed out	1066 ms	45816 KB	Time limit exceeded
26	Execution timed out	1105 ms	148472 KB	Time limit exceeded
27	Execution timed out	1105 ms	223480 KB	Time limit exceeded
28	Execution timed out	1097 ms	87800 KB	Time limit exceeded
29	Execution timed out	1099 ms	92920 KB	Time limit exceeded
30	Execution timed out	1096 ms	68472 KB	Time limit exceeded
31	Execution timed out	1089 ms	74744 KB	Time limit exceeded
32	Execution timed out	1090 ms	77560 KB	Time limit exceeded
33	Execution timed out	1085 ms	48504 KB	Time limit exceeded
34	Execution timed out	1086 ms	74956 KB	Time limit exceeded
35	Execution timed out	1089 ms	54776 KB	Time limit exceeded
36	Execution timed out	1079 ms	70136 KB	Time limit exceeded
37	Execution timed out	1092 ms	40440 KB	Time limit exceeded
38	Execution timed out	1106 ms	207872 KB	Time limit exceeded
39	Execution timed out	1094 ms	47864 KB	Time limit exceeded
40	Execution timed out	1090 ms	102028 KB	Time limit exceeded
41	Execution timed out	1095 ms	93560 KB	Time limit exceeded
42	Runtime error	282 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)