답안 #969884

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969884	2024-04-25T18:13:17 Z	starchan	Bootfall (IZhO17_bootfall)	C++17	65 / 100	1000 ms	13580 KB

bootfall

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
 
const int mod = 1e9+33;
const int SMX = 2e5+5e4+10;
const int MX = 5e5+10;
 
int dp[MX];
 
void add(int x)
{
	for(int i = MX-1; i >= x; i--)
	{
		dp[i]+=dp[i-x];
		dp[i]%=mod;
	}
	return;
}
 
void rem(int x)
{
	for(int i = x; i < MX; i++)
	{
		dp[i]-=dp[i-x]; dp[i]+=mod;
		dp[i]%=mod;
	}
	return;
}
 
int l[MX];
int r[MX];
int st;

void kill(int x)
{
	if(x == st)
		st = r[st];
	else
	{
		r[l[x]] = r[x];
		l[r[x]] = l[x];
	}
}

signed main()
{
	fast();
	for(int i = 1; i < MX; i++)
	{
		l[i] = i-1;
		r[i] = i+1;
	}
	r[0] = 1;
	dp[0] = 1;
	int n;
	cin >> n;
	int S = 0;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i]; S+=a[i];
		add(a[i]);
	}
	if(S%2 || (dp[S/2] == 0))
	{
		cout << "0\n";
		return 0;
	}
	for(int i = 1; i <= n; i++)
	{
		rem(a[i]);
		for(int V = st; V < SMX; V = r[V])
		{
			int D = S+V-a[i];
			if(D%2)
				kill(V);
			if(dp[(D/2)] || ((D >= 2*V) && ((dp[(D/2)-V]))))
				continue;
			kill(V);
		}
		add(a[i]);
	}
	vector<int> v;
	for(int V = st; V < SMX; V = r[V])
		v.pb(V);
	cout << v.size() << "\n";
	for(int x: v)
		cout << x << " ";
	cout << "\n";
	return 0;
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	12120 KB	Output is correct
2	Correct	16 ms	12124 KB	Output is correct
3	Correct	5 ms	12124 KB	Output is correct
4	Correct	13 ms	12164 KB	Output is correct
5	Correct	27 ms	12120 KB	Output is correct
6	Correct	19 ms	12120 KB	Output is correct
7	Correct	16 ms	12124 KB	Output is correct
8	Correct	27 ms	12200 KB	Output is correct
9	Correct	24 ms	12124 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	12120 KB	Output is correct
2	Correct	16 ms	12124 KB	Output is correct
3	Correct	5 ms	12124 KB	Output is correct
4	Correct	13 ms	12164 KB	Output is correct
5	Correct	27 ms	12120 KB	Output is correct
6	Correct	19 ms	12120 KB	Output is correct
7	Correct	16 ms	12124 KB	Output is correct
8	Correct	27 ms	12200 KB	Output is correct
9	Correct	24 ms	12124 KB	Output is correct
10	Correct	66 ms	12172 KB	Output is correct
11	Correct	75 ms	12172 KB	Output is correct
12	Correct	64 ms	12124 KB	Output is correct
13	Correct	60 ms	12124 KB	Output is correct
14	Correct	63 ms	12124 KB	Output is correct
15	Correct	70 ms	12172 KB	Output is correct
16	Correct	75 ms	12120 KB	Output is correct
17	Correct	42 ms	12168 KB	Output is correct
18	Correct	54 ms	12124 KB	Output is correct
19	Correct	67 ms	12124 KB	Output is correct
20	Correct	63 ms	12176 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	12120 KB	Output is correct
2	Correct	16 ms	12124 KB	Output is correct
3	Correct	5 ms	12124 KB	Output is correct
4	Correct	13 ms	12164 KB	Output is correct
5	Correct	27 ms	12120 KB	Output is correct
6	Correct	19 ms	12120 KB	Output is correct
7	Correct	16 ms	12124 KB	Output is correct
8	Correct	27 ms	12200 KB	Output is correct
9	Correct	24 ms	12124 KB	Output is correct
10	Correct	66 ms	12172 KB	Output is correct
11	Correct	75 ms	12172 KB	Output is correct
12	Correct	64 ms	12124 KB	Output is correct
13	Correct	60 ms	12124 KB	Output is correct
14	Correct	63 ms	12124 KB	Output is correct
15	Correct	70 ms	12172 KB	Output is correct
16	Correct	75 ms	12120 KB	Output is correct
17	Correct	42 ms	12168 KB	Output is correct
18	Correct	54 ms	12124 KB	Output is correct
19	Correct	67 ms	12124 KB	Output is correct
20	Correct	63 ms	12176 KB	Output is correct
21	Correct	132 ms	12124 KB	Output is correct
22	Correct	156 ms	12172 KB	Output is correct
23	Correct	107 ms	12124 KB	Output is correct
24	Correct	195 ms	12168 KB	Output is correct
25	Correct	198 ms	12176 KB	Output is correct
26	Correct	199 ms	12176 KB	Output is correct
27	Correct	198 ms	12172 KB	Output is correct
28	Correct	198 ms	12124 KB	Output is correct
29	Correct	208 ms	12376 KB	Output is correct
30	Correct	202 ms	12172 KB	Output is correct
31	Correct	205 ms	12176 KB	Output is correct
32	Correct	202 ms	12120 KB	Output is correct
33	Correct	199 ms	12120 KB	Output is correct
34	Correct	220 ms	12168 KB	Output is correct
35	Correct	198 ms	12124 KB	Output is correct
36	Correct	210 ms	12172 KB	Output is correct

Subtask #4
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	12120 KB	Output is correct
2	Correct	16 ms	12124 KB	Output is correct
3	Correct	5 ms	12124 KB	Output is correct
4	Correct	13 ms	12164 KB	Output is correct
5	Correct	27 ms	12120 KB	Output is correct
6	Correct	19 ms	12120 KB	Output is correct
7	Correct	16 ms	12124 KB	Output is correct
8	Correct	27 ms	12200 KB	Output is correct
9	Correct	24 ms	12124 KB	Output is correct
10	Correct	66 ms	12172 KB	Output is correct
11	Correct	75 ms	12172 KB	Output is correct
12	Correct	64 ms	12124 KB	Output is correct
13	Correct	60 ms	12124 KB	Output is correct
14	Correct	63 ms	12124 KB	Output is correct
15	Correct	70 ms	12172 KB	Output is correct
16	Correct	75 ms	12120 KB	Output is correct
17	Correct	42 ms	12168 KB	Output is correct
18	Correct	54 ms	12124 KB	Output is correct
19	Correct	67 ms	12124 KB	Output is correct
20	Correct	63 ms	12176 KB	Output is correct
21	Correct	132 ms	12124 KB	Output is correct
22	Correct	156 ms	12172 KB	Output is correct
23	Correct	107 ms	12124 KB	Output is correct
24	Correct	195 ms	12168 KB	Output is correct
25	Correct	198 ms	12176 KB	Output is correct
26	Correct	199 ms	12176 KB	Output is correct
27	Correct	198 ms	12172 KB	Output is correct
28	Correct	198 ms	12124 KB	Output is correct
29	Correct	208 ms	12376 KB	Output is correct
30	Correct	202 ms	12172 KB	Output is correct
31	Correct	205 ms	12176 KB	Output is correct
32	Correct	202 ms	12120 KB	Output is correct
33	Correct	199 ms	12120 KB	Output is correct
34	Correct	220 ms	12168 KB	Output is correct
35	Correct	198 ms	12124 KB	Output is correct
36	Correct	210 ms	12172 KB	Output is correct
37	Correct	403 ms	12432 KB	Output is correct
38	Correct	426 ms	12372 KB	Output is correct
39	Correct	491 ms	12172 KB	Output is correct
40	Correct	554 ms	12428 KB	Output is correct
41	Correct	532 ms	12176 KB	Output is correct
42	Correct	496 ms	12424 KB	Output is correct
43	Correct	509 ms	12500 KB	Output is correct
44	Correct	502 ms	12552 KB	Output is correct
45	Correct	526 ms	12496 KB	Output is correct
46	Correct	535 ms	12176 KB	Output is correct
47	Correct	506 ms	12444 KB	Output is correct
48	Correct	501 ms	12560 KB	Output is correct
49	Correct	498 ms	12176 KB	Output is correct
50	Correct	511 ms	12428 KB	Output is correct
51	Correct	161 ms	12124 KB	Output is correct
52	Correct	541 ms	12568 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	12120 KB	Output is correct
2	Correct	16 ms	12124 KB	Output is correct
3	Correct	5 ms	12124 KB	Output is correct
4	Correct	13 ms	12164 KB	Output is correct
5	Correct	27 ms	12120 KB	Output is correct
6	Correct	19 ms	12120 KB	Output is correct
7	Correct	16 ms	12124 KB	Output is correct
8	Correct	27 ms	12200 KB	Output is correct
9	Correct	24 ms	12124 KB	Output is correct
10	Correct	66 ms	12172 KB	Output is correct
11	Correct	75 ms	12172 KB	Output is correct
12	Correct	64 ms	12124 KB	Output is correct
13	Correct	60 ms	12124 KB	Output is correct
14	Correct	63 ms	12124 KB	Output is correct
15	Correct	70 ms	12172 KB	Output is correct
16	Correct	75 ms	12120 KB	Output is correct
17	Correct	42 ms	12168 KB	Output is correct
18	Correct	54 ms	12124 KB	Output is correct
19	Correct	67 ms	12124 KB	Output is correct
20	Correct	63 ms	12176 KB	Output is correct
21	Correct	132 ms	12124 KB	Output is correct
22	Correct	156 ms	12172 KB	Output is correct
23	Correct	107 ms	12124 KB	Output is correct
24	Correct	195 ms	12168 KB	Output is correct
25	Correct	198 ms	12176 KB	Output is correct
26	Correct	199 ms	12176 KB	Output is correct
27	Correct	198 ms	12172 KB	Output is correct
28	Correct	198 ms	12124 KB	Output is correct
29	Correct	208 ms	12376 KB	Output is correct
30	Correct	202 ms	12172 KB	Output is correct
31	Correct	205 ms	12176 KB	Output is correct
32	Correct	202 ms	12120 KB	Output is correct
33	Correct	199 ms	12120 KB	Output is correct
34	Correct	220 ms	12168 KB	Output is correct
35	Correct	198 ms	12124 KB	Output is correct
36	Correct	210 ms	12172 KB	Output is correct
37	Correct	403 ms	12432 KB	Output is correct
38	Correct	426 ms	12372 KB	Output is correct
39	Correct	491 ms	12172 KB	Output is correct
40	Correct	554 ms	12428 KB	Output is correct
41	Correct	532 ms	12176 KB	Output is correct
42	Correct	496 ms	12424 KB	Output is correct
43	Correct	509 ms	12500 KB	Output is correct
44	Correct	502 ms	12552 KB	Output is correct
45	Correct	526 ms	12496 KB	Output is correct
46	Correct	535 ms	12176 KB	Output is correct
47	Correct	506 ms	12444 KB	Output is correct
48	Correct	501 ms	12560 KB	Output is correct
49	Correct	498 ms	12176 KB	Output is correct
50	Correct	511 ms	12428 KB	Output is correct
51	Correct	161 ms	12124 KB	Output is correct
52	Correct	541 ms	12568 KB	Output is correct
53	Correct	599 ms	12556 KB	Output is correct
54	Correct	701 ms	12560 KB	Output is correct
55	Correct	722 ms	13008 KB	Output is correct
56	Correct	618 ms	12756 KB	Output is correct
57	Correct	721 ms	12812 KB	Output is correct
58	Correct	707 ms	12496 KB	Output is correct
59	Correct	705 ms	12812 KB	Output is correct
60	Correct	231 ms	12172 KB	Output is correct
61	Correct	707 ms	12816 KB	Output is correct
62	Correct	656 ms	12812 KB	Output is correct
63	Correct	658 ms	12812 KB	Output is correct
64	Correct	668 ms	12752 KB	Output is correct
65	Correct	628 ms	12124 KB	Output is correct
66	Correct	618 ms	12180 KB	Output is correct

Subtask #6
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	12120 KB	Output is correct
2	Correct	16 ms	12124 KB	Output is correct
3	Correct	5 ms	12124 KB	Output is correct
4	Correct	13 ms	12164 KB	Output is correct
5	Correct	27 ms	12120 KB	Output is correct
6	Correct	19 ms	12120 KB	Output is correct
7	Correct	16 ms	12124 KB	Output is correct
8	Correct	27 ms	12200 KB	Output is correct
9	Correct	24 ms	12124 KB	Output is correct
10	Correct	66 ms	12172 KB	Output is correct
11	Correct	75 ms	12172 KB	Output is correct
12	Correct	64 ms	12124 KB	Output is correct
13	Correct	60 ms	12124 KB	Output is correct
14	Correct	63 ms	12124 KB	Output is correct
15	Correct	70 ms	12172 KB	Output is correct
16	Correct	75 ms	12120 KB	Output is correct
17	Correct	42 ms	12168 KB	Output is correct
18	Correct	54 ms	12124 KB	Output is correct
19	Correct	67 ms	12124 KB	Output is correct
20	Correct	63 ms	12176 KB	Output is correct
21	Correct	132 ms	12124 KB	Output is correct
22	Correct	156 ms	12172 KB	Output is correct
23	Correct	107 ms	12124 KB	Output is correct
24	Correct	195 ms	12168 KB	Output is correct
25	Correct	198 ms	12176 KB	Output is correct
26	Correct	199 ms	12176 KB	Output is correct
27	Correct	198 ms	12172 KB	Output is correct
28	Correct	198 ms	12124 KB	Output is correct
29	Correct	208 ms	12376 KB	Output is correct
30	Correct	202 ms	12172 KB	Output is correct
31	Correct	205 ms	12176 KB	Output is correct
32	Correct	202 ms	12120 KB	Output is correct
33	Correct	199 ms	12120 KB	Output is correct
34	Correct	220 ms	12168 KB	Output is correct
35	Correct	198 ms	12124 KB	Output is correct
36	Correct	210 ms	12172 KB	Output is correct
37	Correct	403 ms	12432 KB	Output is correct
38	Correct	426 ms	12372 KB	Output is correct
39	Correct	491 ms	12172 KB	Output is correct
40	Correct	554 ms	12428 KB	Output is correct
41	Correct	532 ms	12176 KB	Output is correct
42	Correct	496 ms	12424 KB	Output is correct
43	Correct	509 ms	12500 KB	Output is correct
44	Correct	502 ms	12552 KB	Output is correct
45	Correct	526 ms	12496 KB	Output is correct
46	Correct	535 ms	12176 KB	Output is correct
47	Correct	506 ms	12444 KB	Output is correct
48	Correct	501 ms	12560 KB	Output is correct
49	Correct	498 ms	12176 KB	Output is correct
50	Correct	511 ms	12428 KB	Output is correct
51	Correct	161 ms	12124 KB	Output is correct
52	Correct	541 ms	12568 KB	Output is correct
53	Correct	599 ms	12556 KB	Output is correct
54	Correct	701 ms	12560 KB	Output is correct
55	Correct	722 ms	13008 KB	Output is correct
56	Correct	618 ms	12756 KB	Output is correct
57	Correct	721 ms	12812 KB	Output is correct
58	Correct	707 ms	12496 KB	Output is correct
59	Correct	705 ms	12812 KB	Output is correct
60	Correct	231 ms	12172 KB	Output is correct
61	Correct	707 ms	12816 KB	Output is correct
62	Correct	656 ms	12812 KB	Output is correct
63	Correct	658 ms	12812 KB	Output is correct
64	Correct	668 ms	12752 KB	Output is correct
65	Correct	628 ms	12124 KB	Output is correct
66	Correct	618 ms	12180 KB	Output is correct
67	Correct	832 ms	12812 KB	Output is correct
68	Correct	328 ms	12276 KB	Output is correct
69	Execution timed out	1056 ms	13580 KB	Time limit exceeded
70	Halted	0 ms	0 KB	-

답안 #969884

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 15.0 / 15.0

Subtask #4 16.0 / 16.0

Subtask #5 21.0 / 21.0

Subtask #6 0 / 35.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
15.0 / 15.0

Subtask #4
16.0 / 16.0

Subtask #5
21.0 / 21.0

Subtask #6
0 / 35.0