답안 #66176 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66176	2018-08-10T01:13:14 Z	MatheusLealV	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	54.9206 / 100	135 ms	89232 KB

brunhilda

#include <bits/stdc++.h>
#define N 100050
using namespace std;

int n, q, p[N], dp[10000005], prox[10000005];

int solve(int x)
{
	if(!x) return 0;

	if(dp[x] != -1) return dp[x];

	int ans = -2000000000, opt = 0;

	for(int i = n; i >= max(0, n - 100); i--)
	{
		if(x % p[i] == 0) continue;

		if(x % p[i] > ans)
		{
			ans = x % p[i];

			opt = i;
		}
	}

	return dp[x] = opt ? solve(x - ans) + 1: 2000000000;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>q;

	for(int i = 1; i <= n; i++) cin>>p[i];

	sort(p + 1, p + n + 1);

	memset(dp, -1, sizeof dp);

	for(int i = 1, x; i <= q; i++)
	{
		cin>>x;

		int s = solve(x);

		if(s >= 2000000000) cout<<"oo\n";

		else cout<<s<<"\n";

		//print(x);
	}
}

Subtask #1
2.22222222222 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	81 ms	78840 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
2	Runtime error	100 ms	79012 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
3	Runtime error	78 ms	79240 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
4	Runtime error	85 ms	79240 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
5	Runtime error	84 ms	79240 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
6	Runtime error	90 ms	79240 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
7	Runtime error	77 ms	79244 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
8	Runtime error	79 ms	79308 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
9	Runtime error	79 ms	79308 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
10	Runtime error	85 ms	79308 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
11	Runtime error	91 ms	79308 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
12	Runtime error	80 ms	79308 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
13	Correct	34 ms	79308 KB	Output is correct
14	Correct	41 ms	79400 KB	Output is correct
15	Runtime error	89 ms	79400 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
16	Runtime error	95 ms	79400 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
17	Runtime error	76 ms	79400 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
18	Runtime error	78 ms	79400 KB	Execution killed with signal 8 (could be triggered by violating memory limits)

Subtask #2
15.5555555556 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	79400 KB	Output is correct
2	Correct	44 ms	79632 KB	Output is correct
3	Correct	50 ms	79632 KB	Output is correct
4	Incorrect	31 ms	79632 KB	Output isn't correct
5	Correct	39 ms	79632 KB	Output is correct
6	Correct	30 ms	79632 KB	Output is correct
7	Correct	32 ms	79632 KB	Output is correct
8	Correct	30 ms	79632 KB	Output is correct
9	Correct	42 ms	79632 KB	Output is correct
10	Correct	45 ms	79632 KB	Output is correct
11	Incorrect	38 ms	79632 KB	Output isn't correct
12	Correct	30 ms	79632 KB	Output is correct
13	Correct	31 ms	79632 KB	Output is correct
14	Incorrect	30 ms	79632 KB	Output isn't correct
15	Correct	35 ms	79632 KB	Output is correct
16	Correct	45 ms	79632 KB	Output is correct
17	Correct	33 ms	79632 KB	Output is correct
18	Incorrect	49 ms	79632 KB	Output isn't correct

Subtask #3
37.1428571429 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	79732 KB	Output is correct
2	Correct	61 ms	80012 KB	Output is correct
3	Correct	78 ms	80040 KB	Output is correct
4	Incorrect	103 ms	80264 KB	Output isn't correct
5	Correct	126 ms	81156 KB	Output is correct
6	Incorrect	112 ms	81376 KB	Output isn't correct
7	Correct	83 ms	81816 KB	Output is correct
8	Correct	71 ms	81840 KB	Output is correct
9	Correct	71 ms	81992 KB	Output is correct
10	Incorrect	49 ms	81992 KB	Output isn't correct
11	Incorrect	62 ms	81992 KB	Output isn't correct
12	Incorrect	57 ms	81992 KB	Output isn't correct
13	Incorrect	102 ms	82576 KB	Output isn't correct
14	Runtime error	89 ms	82576 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
15	Incorrect	64 ms	82576 KB	Output isn't correct
16	Incorrect	58 ms	82576 KB	Output isn't correct
17	Correct	57 ms	82576 KB	Output is correct
18	Correct	75 ms	82576 KB	Output is correct
19	Correct	54 ms	82576 KB	Output is correct
20	Correct	72 ms	82848 KB	Output is correct
21	Runtime error	77 ms	82848 KB	Execution killed with signal 8 (could be triggered by violating memory limits)
22	Correct	119 ms	83628 KB	Output is correct
23	Correct	107 ms	83980 KB	Output is correct
24	Correct	112 ms	83980 KB	Output is correct
25	Incorrect	117 ms	84404 KB	Output isn't correct
26	Incorrect	123 ms	84404 KB	Output isn't correct
27	Correct	86 ms	84792 KB	Output is correct
28	Correct	102 ms	84792 KB	Output is correct
29	Correct	125 ms	85544 KB	Output is correct
30	Correct	124 ms	86152 KB	Output is correct
31	Correct	108 ms	86152 KB	Output is correct
32	Correct	114 ms	86152 KB	Output is correct
33	Incorrect	114 ms	86232 KB	Output isn't correct
34	Correct	78 ms	86688 KB	Output is correct
35	Correct	99 ms	86688 KB	Output is correct
36	Correct	135 ms	87224 KB	Output is correct
37	Correct	124 ms	87880 KB	Output is correct
38	Incorrect	104 ms	88228 KB	Output isn't correct
39	Incorrect	107 ms	88284 KB	Output isn't correct
40	Correct	111 ms	88684 KB	Output is correct
41	Correct	84 ms	89084 KB	Output is correct
42	Incorrect	102 ms	89232 KB	Output isn't correct

답안 #66176

Compilation message

Subtask #1 2.22222222222 / 20.0

Subtask #2 15.5555555556 / 20.0

Subtask #3 37.1428571429 / 60.0

Subtask #1
2.22222222222 / 20.0

Subtask #2
15.5555555556 / 20.0

Subtask #3
37.1428571429 / 60.0