답안 #888393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888393	2023-12-17T09:10:01 Z	pcc	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1000 ms	4708 KB

bootfall

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 510;
const int C = mxn*mxn;
int mod = 998244353;
int arr[mxn];
int dp[C];
int del[C];
int n;
int sum = 0;
bitset<C> able;
vector<int> ans;

inline int mad(int a,int b){
	a += b;
	return a>=mod?a-mod:a;
}
inline int mub(int a,int b){
	return mad(a,mod-b);
}

inline bool check(int now,int tsum){
	if(sum&1)return false;
	if(!dp[sum>>1])return false;
	if(tsum&1)return false;
	if(now+now>tsum)return false;
	if(!del[tsum>>1])return false;
	return true;
}

inline void relax(int tar){
	mod = tar;
	memset(dp,0,sizeof(dp));
	dp[0] = 1;
	able.set();
	for(int i = 1;i<=n;i++){
		for(int j = C-1;j>=arr[i];j--)dp[j] = mad(dp[j],dp[j-arr[i]]);
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<C;j++)del[j] = dp[j];
		for(int j = arr[i];j<C;j++)del[j] = mub(del[j],del[j-arr[i]]);
		for(int j = 1;j<=sum;j++){
			if(!check(j,sum-arr[i]+j))able[j] = false;
		}
	}
	for(int j = 1;j<=sum;j++)if(able[j])ans.push_back(j);
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	dp[0] = 1;
	for(int i = 1;i<=n;i++){
		cin>>arr[i];
		sum += arr[i];
	}

	relax((int)1e9+7);
	relax((int)712271227);
	relax((int)1e8+7);
	relax(113);
	relax(998244353);
	relax(101010111);


	/*
	for(int i = 0;i<=10;i++)cout<<dp[i]<<' ';cout<<endl;
	cout<<sum<<endl;
	cout<<endl;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<=10;j++)cout<<del[i][j]<<' ';cout<<endl;
	}
   */
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());

	cout<<ans.size()<<'\n';
	for(auto &i:ans)cout<<i<<' ';
	return 0;
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	2392 KB	Output is correct
2	Correct	15 ms	2396 KB	Output is correct
3	Correct	12 ms	2524 KB	Output is correct
4	Correct	5 ms	2396 KB	Output is correct
5	Correct	17 ms	2396 KB	Output is correct
6	Correct	16 ms	2396 KB	Output is correct
7	Correct	8 ms	2396 KB	Output is correct
8	Correct	15 ms	2396 KB	Output is correct
9	Correct	13 ms	2528 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	2392 KB	Output is correct
2	Correct	15 ms	2396 KB	Output is correct
3	Correct	12 ms	2524 KB	Output is correct
4	Correct	5 ms	2396 KB	Output is correct
5	Correct	17 ms	2396 KB	Output is correct
6	Correct	16 ms	2396 KB	Output is correct
7	Correct	8 ms	2396 KB	Output is correct
8	Correct	15 ms	2396 KB	Output is correct
9	Correct	13 ms	2528 KB	Output is correct
10	Correct	50 ms	2504 KB	Output is correct
11	Correct	83 ms	2644 KB	Output is correct
12	Correct	60 ms	2392 KB	Output is correct
13	Correct	65 ms	2500 KB	Output is correct
14	Correct	65 ms	2396 KB	Output is correct
15	Correct	78 ms	2396 KB	Output is correct
16	Correct	86 ms	2500 KB	Output is correct
17	Correct	43 ms	2392 KB	Output is correct
18	Correct	56 ms	2396 KB	Output is correct
19	Correct	65 ms	2392 KB	Output is correct
20	Correct	45 ms	2396 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	2392 KB	Output is correct
2	Correct	15 ms	2396 KB	Output is correct
3	Correct	12 ms	2524 KB	Output is correct
4	Correct	5 ms	2396 KB	Output is correct
5	Correct	17 ms	2396 KB	Output is correct
6	Correct	16 ms	2396 KB	Output is correct
7	Correct	8 ms	2396 KB	Output is correct
8	Correct	15 ms	2396 KB	Output is correct
9	Correct	13 ms	2528 KB	Output is correct
10	Correct	50 ms	2504 KB	Output is correct
11	Correct	83 ms	2644 KB	Output is correct
12	Correct	60 ms	2392 KB	Output is correct
13	Correct	65 ms	2500 KB	Output is correct
14	Correct	65 ms	2396 KB	Output is correct
15	Correct	78 ms	2396 KB	Output is correct
16	Correct	86 ms	2500 KB	Output is correct
17	Correct	43 ms	2392 KB	Output is correct
18	Correct	56 ms	2396 KB	Output is correct
19	Correct	65 ms	2392 KB	Output is correct
20	Correct	45 ms	2396 KB	Output is correct
21	Correct	90 ms	2396 KB	Output is correct
22	Correct	107 ms	2536 KB	Output is correct
23	Correct	76 ms	2644 KB	Output is correct
24	Correct	142 ms	2392 KB	Output is correct
25	Correct	101 ms	2612 KB	Output is correct
26	Correct	106 ms	2548 KB	Output is correct
27	Correct	109 ms	2392 KB	Output is correct
28	Correct	108 ms	2532 KB	Output is correct
29	Correct	107 ms	2516 KB	Output is correct
30	Correct	128 ms	2500 KB	Output is correct
31	Correct	108 ms	3032 KB	Output is correct
32	Correct	143 ms	2392 KB	Output is correct
33	Correct	111 ms	2500 KB	Output is correct
34	Correct	110 ms	2504 KB	Output is correct
35	Correct	109 ms	2520 KB	Output is correct
36	Correct	155 ms	2556 KB	Output is correct

Subtask #4
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	2392 KB	Output is correct
2	Correct	15 ms	2396 KB	Output is correct
3	Correct	12 ms	2524 KB	Output is correct
4	Correct	5 ms	2396 KB	Output is correct
5	Correct	17 ms	2396 KB	Output is correct
6	Correct	16 ms	2396 KB	Output is correct
7	Correct	8 ms	2396 KB	Output is correct
8	Correct	15 ms	2396 KB	Output is correct
9	Correct	13 ms	2528 KB	Output is correct
10	Correct	50 ms	2504 KB	Output is correct
11	Correct	83 ms	2644 KB	Output is correct
12	Correct	60 ms	2392 KB	Output is correct
13	Correct	65 ms	2500 KB	Output is correct
14	Correct	65 ms	2396 KB	Output is correct
15	Correct	78 ms	2396 KB	Output is correct
16	Correct	86 ms	2500 KB	Output is correct
17	Correct	43 ms	2392 KB	Output is correct
18	Correct	56 ms	2396 KB	Output is correct
19	Correct	65 ms	2392 KB	Output is correct
20	Correct	45 ms	2396 KB	Output is correct
21	Correct	90 ms	2396 KB	Output is correct
22	Correct	107 ms	2536 KB	Output is correct
23	Correct	76 ms	2644 KB	Output is correct
24	Correct	142 ms	2392 KB	Output is correct
25	Correct	101 ms	2612 KB	Output is correct
26	Correct	106 ms	2548 KB	Output is correct
27	Correct	109 ms	2392 KB	Output is correct
28	Correct	108 ms	2532 KB	Output is correct
29	Correct	107 ms	2516 KB	Output is correct
30	Correct	128 ms	2500 KB	Output is correct
31	Correct	108 ms	3032 KB	Output is correct
32	Correct	143 ms	2392 KB	Output is correct
33	Correct	111 ms	2500 KB	Output is correct
34	Correct	110 ms	2504 KB	Output is correct
35	Correct	109 ms	2520 KB	Output is correct
36	Correct	155 ms	2556 KB	Output is correct
37	Correct	222 ms	2772 KB	Output is correct
38	Correct	229 ms	2900 KB	Output is correct
39	Correct	431 ms	2508 KB	Output is correct
40	Correct	367 ms	3304 KB	Output is correct
41	Correct	503 ms	2500 KB	Output is correct
42	Correct	343 ms	3304 KB	Output is correct
43	Correct	333 ms	3456 KB	Output is correct
44	Correct	343 ms	3464 KB	Output is correct
45	Correct	343 ms	3536 KB	Output is correct
46	Correct	380 ms	2500 KB	Output is correct
47	Correct	331 ms	3032 KB	Output is correct
48	Correct	370 ms	3316 KB	Output is correct
49	Correct	396 ms	2640 KB	Output is correct
50	Correct	346 ms	3232 KB	Output is correct
51	Correct	352 ms	2500 KB	Output is correct
52	Correct	402 ms	3796 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	2392 KB	Output is correct
2	Correct	15 ms	2396 KB	Output is correct
3	Correct	12 ms	2524 KB	Output is correct
4	Correct	5 ms	2396 KB	Output is correct
5	Correct	17 ms	2396 KB	Output is correct
6	Correct	16 ms	2396 KB	Output is correct
7	Correct	8 ms	2396 KB	Output is correct
8	Correct	15 ms	2396 KB	Output is correct
9	Correct	13 ms	2528 KB	Output is correct
10	Correct	50 ms	2504 KB	Output is correct
11	Correct	83 ms	2644 KB	Output is correct
12	Correct	60 ms	2392 KB	Output is correct
13	Correct	65 ms	2500 KB	Output is correct
14	Correct	65 ms	2396 KB	Output is correct
15	Correct	78 ms	2396 KB	Output is correct
16	Correct	86 ms	2500 KB	Output is correct
17	Correct	43 ms	2392 KB	Output is correct
18	Correct	56 ms	2396 KB	Output is correct
19	Correct	65 ms	2392 KB	Output is correct
20	Correct	45 ms	2396 KB	Output is correct
21	Correct	90 ms	2396 KB	Output is correct
22	Correct	107 ms	2536 KB	Output is correct
23	Correct	76 ms	2644 KB	Output is correct
24	Correct	142 ms	2392 KB	Output is correct
25	Correct	101 ms	2612 KB	Output is correct
26	Correct	106 ms	2548 KB	Output is correct
27	Correct	109 ms	2392 KB	Output is correct
28	Correct	108 ms	2532 KB	Output is correct
29	Correct	107 ms	2516 KB	Output is correct
30	Correct	128 ms	2500 KB	Output is correct
31	Correct	108 ms	3032 KB	Output is correct
32	Correct	143 ms	2392 KB	Output is correct
33	Correct	111 ms	2500 KB	Output is correct
34	Correct	110 ms	2504 KB	Output is correct
35	Correct	109 ms	2520 KB	Output is correct
36	Correct	155 ms	2556 KB	Output is correct
37	Correct	222 ms	2772 KB	Output is correct
38	Correct	229 ms	2900 KB	Output is correct
39	Correct	431 ms	2508 KB	Output is correct
40	Correct	367 ms	3304 KB	Output is correct
41	Correct	503 ms	2500 KB	Output is correct
42	Correct	343 ms	3304 KB	Output is correct
43	Correct	333 ms	3456 KB	Output is correct
44	Correct	343 ms	3464 KB	Output is correct
45	Correct	343 ms	3536 KB	Output is correct
46	Correct	380 ms	2500 KB	Output is correct
47	Correct	331 ms	3032 KB	Output is correct
48	Correct	370 ms	3316 KB	Output is correct
49	Correct	396 ms	2640 KB	Output is correct
50	Correct	346 ms	3232 KB	Output is correct
51	Correct	352 ms	2500 KB	Output is correct
52	Correct	402 ms	3796 KB	Output is correct
53	Correct	395 ms	3076 KB	Output is correct
54	Correct	476 ms	3672 KB	Output is correct
55	Correct	628 ms	4700 KB	Output is correct
56	Correct	417 ms	3632 KB	Output is correct
57	Correct	628 ms	4708 KB	Output is correct
58	Correct	524 ms	3768 KB	Output is correct
59	Correct	522 ms	3540 KB	Output is correct
60	Correct	582 ms	2644 KB	Output is correct
61	Correct	540 ms	3788 KB	Output is correct
62	Correct	535 ms	3816 KB	Output is correct
63	Correct	543 ms	4676 KB	Output is correct
64	Correct	526 ms	4700 KB	Output is correct
65	Correct	513 ms	2568 KB	Output is correct
66	Correct	515 ms	2632 KB	Output is correct

Subtask #6
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	2392 KB	Output is correct
2	Correct	15 ms	2396 KB	Output is correct
3	Correct	12 ms	2524 KB	Output is correct
4	Correct	5 ms	2396 KB	Output is correct
5	Correct	17 ms	2396 KB	Output is correct
6	Correct	16 ms	2396 KB	Output is correct
7	Correct	8 ms	2396 KB	Output is correct
8	Correct	15 ms	2396 KB	Output is correct
9	Correct	13 ms	2528 KB	Output is correct
10	Correct	50 ms	2504 KB	Output is correct
11	Correct	83 ms	2644 KB	Output is correct
12	Correct	60 ms	2392 KB	Output is correct
13	Correct	65 ms	2500 KB	Output is correct
14	Correct	65 ms	2396 KB	Output is correct
15	Correct	78 ms	2396 KB	Output is correct
16	Correct	86 ms	2500 KB	Output is correct
17	Correct	43 ms	2392 KB	Output is correct
18	Correct	56 ms	2396 KB	Output is correct
19	Correct	65 ms	2392 KB	Output is correct
20	Correct	45 ms	2396 KB	Output is correct
21	Correct	90 ms	2396 KB	Output is correct
22	Correct	107 ms	2536 KB	Output is correct
23	Correct	76 ms	2644 KB	Output is correct
24	Correct	142 ms	2392 KB	Output is correct
25	Correct	101 ms	2612 KB	Output is correct
26	Correct	106 ms	2548 KB	Output is correct
27	Correct	109 ms	2392 KB	Output is correct
28	Correct	108 ms	2532 KB	Output is correct
29	Correct	107 ms	2516 KB	Output is correct
30	Correct	128 ms	2500 KB	Output is correct
31	Correct	108 ms	3032 KB	Output is correct
32	Correct	143 ms	2392 KB	Output is correct
33	Correct	111 ms	2500 KB	Output is correct
34	Correct	110 ms	2504 KB	Output is correct
35	Correct	109 ms	2520 KB	Output is correct
36	Correct	155 ms	2556 KB	Output is correct
37	Correct	222 ms	2772 KB	Output is correct
38	Correct	229 ms	2900 KB	Output is correct
39	Correct	431 ms	2508 KB	Output is correct
40	Correct	367 ms	3304 KB	Output is correct
41	Correct	503 ms	2500 KB	Output is correct
42	Correct	343 ms	3304 KB	Output is correct
43	Correct	333 ms	3456 KB	Output is correct
44	Correct	343 ms	3464 KB	Output is correct
45	Correct	343 ms	3536 KB	Output is correct
46	Correct	380 ms	2500 KB	Output is correct
47	Correct	331 ms	3032 KB	Output is correct
48	Correct	370 ms	3316 KB	Output is correct
49	Correct	396 ms	2640 KB	Output is correct
50	Correct	346 ms	3232 KB	Output is correct
51	Correct	352 ms	2500 KB	Output is correct
52	Correct	402 ms	3796 KB	Output is correct
53	Correct	395 ms	3076 KB	Output is correct
54	Correct	476 ms	3672 KB	Output is correct
55	Correct	628 ms	4700 KB	Output is correct
56	Correct	417 ms	3632 KB	Output is correct
57	Correct	628 ms	4708 KB	Output is correct
58	Correct	524 ms	3768 KB	Output is correct
59	Correct	522 ms	3540 KB	Output is correct
60	Correct	582 ms	2644 KB	Output is correct
61	Correct	540 ms	3788 KB	Output is correct
62	Correct	535 ms	3816 KB	Output is correct
63	Correct	543 ms	4676 KB	Output is correct
64	Correct	526 ms	4700 KB	Output is correct
65	Correct	513 ms	2568 KB	Output is correct
66	Correct	515 ms	2632 KB	Output is correct
67	Correct	647 ms	3648 KB	Output is correct
68	Execution timed out	1066 ms	2388 KB	Time limit exceeded
69	Halted	0 ms	0 KB	-

답안 #888393

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