답안 #91295 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91295	2018-12-27T03:59:49 Z	Atashka01	Bootfall (IZhO17_bootfall)	C++11	100 / 100	740 ms	5080 KB

bootfall

//Euzibillahiminesseytanirracim Bismillahirrahmanirrahim

/*
ID:
TASK:
LANG: C++
*/

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define PII pair<int,int>
#define inf 1000000001
using namespace std;

const int N = 250505;

int n, a[501], dp[N], d[N], k[N];

vector<int>v;

int main()
{
	
	cin>>n;
	
	int jem = 0;
	
	for(int i=1;i<=n;i++) {
		
		cin>>a[i];
		jem += a[i];
		
	}
	
	dp[0] = 1;
	
	for(int i=1;i<=n;i++){
		
		for(int j=N;j>=0;j--) dp[j + a[i]] += dp[j];
		
	}
	
	if(jem % 2 != 0 || dp[jem / 2] == 0) return cout<<"0", 0;
	
	for(int i=1;i<=n;i++){
		
		int ans = jem - a[i];
		
		memset(d , 0 , sizeof(d));
		
		for(int j=0;j<=N;j++){
			
			d[j] += dp[j];
			d[j + a[i]] -= d[j];
			
		}
		
		for(int j=0;j<=N;j++){
			
			if( (ans + j) % 2 == 0 && ans - j >= 0 && ( d[(ans - j) / 2] != 0) ){
				
				k[j]++;
				if(k[j] == n) v.pb(j);
				
			}
			
		}
		
	}
	
	cout<<v.size()<<"\n";
	for(auto x:v) cout<<x<<" ";
	
}

/*
6
3 5 7 11 9 13
_________oBBBBB8o   oBBBBBBB8
_____o8BBBBBBBBBBB  BBBBBBBBB8        o88o
___o8BBBBBB**8BBBB  BBBBBBBBBB     oBBBBBBBo
__oBBBBBBB*   ***   BBBBBBBBBB     BBBBBBBBBBo
_8BBBBBBBBBBooooo   *BBBBBBB8      *BB* 8BBBBBBo
_8BBBBBBBBBBBBBBBB8ooBBBBBBB8           8BBBBBBB8
__*BBBBBBBBBBBBBBBBBBBBBBBBBB8 o88BB88BBBBBBBBBBBB
____*BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB8
______**8BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB*
___________*BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB8*
____________*BBBBBBBBBBBBBBBBBBBBBBBB8888**
_____________BBBBBBBBBBBBBBBBBBBBBBB*
_____________*BBBBBBBBBBBBBBBBBBBBB*
______________*BBBBBBBBBBBBBBBBBB8
_______________*BBBBBBBBBBBBBBBB*
________________8BBBBBBBBBBBBBBB8
_________________8BBBBBBBBBBBBBBBo
__________________BBBBBBBBBBBBBBB8
__________________BBBBBBBBBBBBBBBB
__________________8BBBBBBBBBBBBBBB8
__________________*BBBBBBBBBBBBBBBB
__________________8BBBBBBBBBBBBBBBB8
_________________oBBBBBBBBBBBBBBBBBB
________________oBBBBBBBBBBBBBBBBBBB
________________BBBBBBBBBBBBBBBBBBBB
_______________8BBBBBBBBBBBBBBBBBBB8
______________oBBBBBBBBB88BBBBBBBBB8
______________8BBBBBBBBB*8BBBBBBBBB*
______________BBBBBBBBB* BBBBBBBBB8
______________BBBBBBBB8 oBBBBBBBBB*
______________8BBBBBBB  oBBBBBBBB*
______________BBBBBBB*  8BBBBBBB*
_____________8BBBBBB*   BBBBBBB*
____________8BBBBBB8   oBBBBBB8
___________8BBBBBB8    8BBBBBB*
__________oBBBBBB8    BBBBBBB8
__________BBBBBBB8   BBBBBBBB*
_________oBBBBBBB8   BBBBBBBB
_________8BBBBBB8    BBBBBBB*
_________BBBBBB*     8BBBBB*
________oBBBB8       BBBBB*
________oBBB8        BBBB*
________BBBB8       8BBBBo
_______8BBBB*      oBBBBBBo
______8BBBB*       *BBBBBBBB8o
______BBBBB*            *88BBBo
*/

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:57:9: warning: iteration 250505 invokes undefined behavior [-Waggressive-loop-optimizations]
    d[j] += dp[j];
    ~~~~~^~~~~~~~
bootfall.cpp:55:16: note: within this loop
   for(int j=0;j<=N;j++){
               ~^~~

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	2424 KB	Output is correct
2	Correct	13 ms	2432 KB	Output is correct
3	Correct	3 ms	2432 KB	Output is correct
4	Correct	11 ms	2432 KB	Output is correct
5	Correct	24 ms	2448 KB	Output is correct
6	Correct	17 ms	2532 KB	Output is correct
7	Correct	14 ms	2532 KB	Output is correct
8	Correct	27 ms	2628 KB	Output is correct
9	Correct	21 ms	2628 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	2424 KB	Output is correct
2	Correct	13 ms	2432 KB	Output is correct
3	Correct	3 ms	2432 KB	Output is correct
4	Correct	11 ms	2432 KB	Output is correct
5	Correct	24 ms	2448 KB	Output is correct
6	Correct	17 ms	2532 KB	Output is correct
7	Correct	14 ms	2532 KB	Output is correct
8	Correct	27 ms	2628 KB	Output is correct
9	Correct	21 ms	2628 KB	Output is correct
10	Correct	59 ms	2628 KB	Output is correct
11	Correct	57 ms	2628 KB	Output is correct
12	Correct	53 ms	2628 KB	Output is correct
13	Correct	52 ms	2628 KB	Output is correct
14	Correct	57 ms	2628 KB	Output is correct
15	Correct	60 ms	2628 KB	Output is correct
16	Correct	63 ms	2644 KB	Output is correct
17	Correct	38 ms	2644 KB	Output is correct
18	Correct	43 ms	2644 KB	Output is correct
19	Correct	50 ms	2660 KB	Output is correct
20	Correct	60 ms	2664 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	2424 KB	Output is correct
2	Correct	13 ms	2432 KB	Output is correct
3	Correct	3 ms	2432 KB	Output is correct
4	Correct	11 ms	2432 KB	Output is correct
5	Correct	24 ms	2448 KB	Output is correct
6	Correct	17 ms	2532 KB	Output is correct
7	Correct	14 ms	2532 KB	Output is correct
8	Correct	27 ms	2628 KB	Output is correct
9	Correct	21 ms	2628 KB	Output is correct
10	Correct	59 ms	2628 KB	Output is correct
11	Correct	57 ms	2628 KB	Output is correct
12	Correct	53 ms	2628 KB	Output is correct
13	Correct	52 ms	2628 KB	Output is correct
14	Correct	57 ms	2628 KB	Output is correct
15	Correct	60 ms	2628 KB	Output is correct
16	Correct	63 ms	2644 KB	Output is correct
17	Correct	38 ms	2644 KB	Output is correct
18	Correct	43 ms	2644 KB	Output is correct
19	Correct	50 ms	2660 KB	Output is correct
20	Correct	60 ms	2664 KB	Output is correct
21	Correct	124 ms	2756 KB	Output is correct
22	Correct	145 ms	2760 KB	Output is correct
23	Correct	98 ms	2760 KB	Output is correct
24	Correct	165 ms	2760 KB	Output is correct
25	Correct	175 ms	2820 KB	Output is correct
26	Correct	198 ms	2820 KB	Output is correct
27	Correct	188 ms	2820 KB	Output is correct
28	Correct	169 ms	2832 KB	Output is correct
29	Correct	190 ms	2836 KB	Output is correct
30	Correct	190 ms	2836 KB	Output is correct
31	Correct	175 ms	2836 KB	Output is correct
32	Correct	181 ms	2836 KB	Output is correct
33	Correct	195 ms	2836 KB	Output is correct
34	Correct	195 ms	2852 KB	Output is correct
35	Correct	182 ms	2852 KB	Output is correct
36	Correct	180 ms	2864 KB	Output is correct

Subtask #4
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	2424 KB	Output is correct
2	Correct	13 ms	2432 KB	Output is correct
3	Correct	3 ms	2432 KB	Output is correct
4	Correct	11 ms	2432 KB	Output is correct
5	Correct	24 ms	2448 KB	Output is correct
6	Correct	17 ms	2532 KB	Output is correct
7	Correct	14 ms	2532 KB	Output is correct
8	Correct	27 ms	2628 KB	Output is correct
9	Correct	21 ms	2628 KB	Output is correct
10	Correct	59 ms	2628 KB	Output is correct
11	Correct	57 ms	2628 KB	Output is correct
12	Correct	53 ms	2628 KB	Output is correct
13	Correct	52 ms	2628 KB	Output is correct
14	Correct	57 ms	2628 KB	Output is correct
15	Correct	60 ms	2628 KB	Output is correct
16	Correct	63 ms	2644 KB	Output is correct
17	Correct	38 ms	2644 KB	Output is correct
18	Correct	43 ms	2644 KB	Output is correct
19	Correct	50 ms	2660 KB	Output is correct
20	Correct	60 ms	2664 KB	Output is correct
21	Correct	124 ms	2756 KB	Output is correct
22	Correct	145 ms	2760 KB	Output is correct
23	Correct	98 ms	2760 KB	Output is correct
24	Correct	165 ms	2760 KB	Output is correct
25	Correct	175 ms	2820 KB	Output is correct
26	Correct	198 ms	2820 KB	Output is correct
27	Correct	188 ms	2820 KB	Output is correct
28	Correct	169 ms	2832 KB	Output is correct
29	Correct	190 ms	2836 KB	Output is correct
30	Correct	190 ms	2836 KB	Output is correct
31	Correct	175 ms	2836 KB	Output is correct
32	Correct	181 ms	2836 KB	Output is correct
33	Correct	195 ms	2836 KB	Output is correct
34	Correct	195 ms	2852 KB	Output is correct
35	Correct	182 ms	2852 KB	Output is correct
36	Correct	180 ms	2864 KB	Output is correct
37	Correct	357 ms	2976 KB	Output is correct
38	Correct	375 ms	2984 KB	Output is correct
39	Correct	429 ms	3004 KB	Output is correct
40	Correct	469 ms	3004 KB	Output is correct
41	Correct	450 ms	3072 KB	Output is correct
42	Correct	423 ms	3140 KB	Output is correct
43	Correct	411 ms	3392 KB	Output is correct
44	Correct	428 ms	3404 KB	Output is correct
45	Correct	434 ms	3404 KB	Output is correct
46	Correct	484 ms	3404 KB	Output is correct
47	Correct	420 ms	3404 KB	Output is correct
48	Correct	437 ms	3404 KB	Output is correct
49	Correct	406 ms	3404 KB	Output is correct
50	Correct	413 ms	3404 KB	Output is correct
51	Correct	36 ms	3404 KB	Output is correct
52	Correct	408 ms	3452 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	2424 KB	Output is correct
2	Correct	13 ms	2432 KB	Output is correct
3	Correct	3 ms	2432 KB	Output is correct
4	Correct	11 ms	2432 KB	Output is correct
5	Correct	24 ms	2448 KB	Output is correct
6	Correct	17 ms	2532 KB	Output is correct
7	Correct	14 ms	2532 KB	Output is correct
8	Correct	27 ms	2628 KB	Output is correct
9	Correct	21 ms	2628 KB	Output is correct
10	Correct	59 ms	2628 KB	Output is correct
11	Correct	57 ms	2628 KB	Output is correct
12	Correct	53 ms	2628 KB	Output is correct
13	Correct	52 ms	2628 KB	Output is correct
14	Correct	57 ms	2628 KB	Output is correct
15	Correct	60 ms	2628 KB	Output is correct
16	Correct	63 ms	2644 KB	Output is correct
17	Correct	38 ms	2644 KB	Output is correct
18	Correct	43 ms	2644 KB	Output is correct
19	Correct	50 ms	2660 KB	Output is correct
20	Correct	60 ms	2664 KB	Output is correct
21	Correct	124 ms	2756 KB	Output is correct
22	Correct	145 ms	2760 KB	Output is correct
23	Correct	98 ms	2760 KB	Output is correct
24	Correct	165 ms	2760 KB	Output is correct
25	Correct	175 ms	2820 KB	Output is correct
26	Correct	198 ms	2820 KB	Output is correct
27	Correct	188 ms	2820 KB	Output is correct
28	Correct	169 ms	2832 KB	Output is correct
29	Correct	190 ms	2836 KB	Output is correct
30	Correct	190 ms	2836 KB	Output is correct
31	Correct	175 ms	2836 KB	Output is correct
32	Correct	181 ms	2836 KB	Output is correct
33	Correct	195 ms	2836 KB	Output is correct
34	Correct	195 ms	2852 KB	Output is correct
35	Correct	182 ms	2852 KB	Output is correct
36	Correct	180 ms	2864 KB	Output is correct
37	Correct	357 ms	2976 KB	Output is correct
38	Correct	375 ms	2984 KB	Output is correct
39	Correct	429 ms	3004 KB	Output is correct
40	Correct	469 ms	3004 KB	Output is correct
41	Correct	450 ms	3072 KB	Output is correct
42	Correct	423 ms	3140 KB	Output is correct
43	Correct	411 ms	3392 KB	Output is correct
44	Correct	428 ms	3404 KB	Output is correct
45	Correct	434 ms	3404 KB	Output is correct
46	Correct	484 ms	3404 KB	Output is correct
47	Correct	420 ms	3404 KB	Output is correct
48	Correct	437 ms	3404 KB	Output is correct
49	Correct	406 ms	3404 KB	Output is correct
50	Correct	413 ms	3404 KB	Output is correct
51	Correct	36 ms	3404 KB	Output is correct
52	Correct	408 ms	3452 KB	Output is correct
53	Correct	517 ms	3452 KB	Output is correct
54	Correct	583 ms	3460 KB	Output is correct
55	Correct	515 ms	3972 KB	Output is correct
56	Correct	528 ms	3972 KB	Output is correct
57	Correct	513 ms	4008 KB	Output is correct
58	Correct	578 ms	4008 KB	Output is correct
59	Correct	575 ms	4008 KB	Output is correct
60	Correct	59 ms	4008 KB	Output is correct
61	Correct	544 ms	4008 KB	Output is correct
62	Correct	486 ms	4008 KB	Output is correct
63	Correct	481 ms	4008 KB	Output is correct
64	Correct	516 ms	4008 KB	Output is correct
65	Correct	564 ms	4008 KB	Output is correct
66	Correct	501 ms	4008 KB	Output is correct

Subtask #6
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	2424 KB	Output is correct
2	Correct	13 ms	2432 KB	Output is correct
3	Correct	3 ms	2432 KB	Output is correct
4	Correct	11 ms	2432 KB	Output is correct
5	Correct	24 ms	2448 KB	Output is correct
6	Correct	17 ms	2532 KB	Output is correct
7	Correct	14 ms	2532 KB	Output is correct
8	Correct	27 ms	2628 KB	Output is correct
9	Correct	21 ms	2628 KB	Output is correct
10	Correct	59 ms	2628 KB	Output is correct
11	Correct	57 ms	2628 KB	Output is correct
12	Correct	53 ms	2628 KB	Output is correct
13	Correct	52 ms	2628 KB	Output is correct
14	Correct	57 ms	2628 KB	Output is correct
15	Correct	60 ms	2628 KB	Output is correct
16	Correct	63 ms	2644 KB	Output is correct
17	Correct	38 ms	2644 KB	Output is correct
18	Correct	43 ms	2644 KB	Output is correct
19	Correct	50 ms	2660 KB	Output is correct
20	Correct	60 ms	2664 KB	Output is correct
21	Correct	124 ms	2756 KB	Output is correct
22	Correct	145 ms	2760 KB	Output is correct
23	Correct	98 ms	2760 KB	Output is correct
24	Correct	165 ms	2760 KB	Output is correct
25	Correct	175 ms	2820 KB	Output is correct
26	Correct	198 ms	2820 KB	Output is correct
27	Correct	188 ms	2820 KB	Output is correct
28	Correct	169 ms	2832 KB	Output is correct
29	Correct	190 ms	2836 KB	Output is correct
30	Correct	190 ms	2836 KB	Output is correct
31	Correct	175 ms	2836 KB	Output is correct
32	Correct	181 ms	2836 KB	Output is correct
33	Correct	195 ms	2836 KB	Output is correct
34	Correct	195 ms	2852 KB	Output is correct
35	Correct	182 ms	2852 KB	Output is correct
36	Correct	180 ms	2864 KB	Output is correct
37	Correct	357 ms	2976 KB	Output is correct
38	Correct	375 ms	2984 KB	Output is correct
39	Correct	429 ms	3004 KB	Output is correct
40	Correct	469 ms	3004 KB	Output is correct
41	Correct	450 ms	3072 KB	Output is correct
42	Correct	423 ms	3140 KB	Output is correct
43	Correct	411 ms	3392 KB	Output is correct
44	Correct	428 ms	3404 KB	Output is correct
45	Correct	434 ms	3404 KB	Output is correct
46	Correct	484 ms	3404 KB	Output is correct
47	Correct	420 ms	3404 KB	Output is correct
48	Correct	437 ms	3404 KB	Output is correct
49	Correct	406 ms	3404 KB	Output is correct
50	Correct	413 ms	3404 KB	Output is correct
51	Correct	36 ms	3404 KB	Output is correct
52	Correct	408 ms	3452 KB	Output is correct
53	Correct	517 ms	3452 KB	Output is correct
54	Correct	583 ms	3460 KB	Output is correct
55	Correct	515 ms	3972 KB	Output is correct
56	Correct	528 ms	3972 KB	Output is correct
57	Correct	513 ms	4008 KB	Output is correct
58	Correct	578 ms	4008 KB	Output is correct
59	Correct	575 ms	4008 KB	Output is correct
60	Correct	59 ms	4008 KB	Output is correct
61	Correct	544 ms	4008 KB	Output is correct
62	Correct	486 ms	4008 KB	Output is correct
63	Correct	481 ms	4008 KB	Output is correct
64	Correct	516 ms	4008 KB	Output is correct
65	Correct	564 ms	4008 KB	Output is correct
66	Correct	501 ms	4008 KB	Output is correct
67	Correct	622 ms	4008 KB	Output is correct
68	Correct	73 ms	4008 KB	Output is correct
69	Correct	614 ms	4932 KB	Output is correct
70	Correct	711 ms	4932 KB	Output is correct
71	Correct	740 ms	4932 KB	Output is correct
72	Correct	717 ms	4932 KB	Output is correct
73	Correct	713 ms	4932 KB	Output is correct
74	Correct	573 ms	5060 KB	Output is correct
75	Correct	667 ms	5060 KB	Output is correct
76	Correct	551 ms	5080 KB	Output is correct
77	Correct	545 ms	5080 KB	Output is correct

답안 #91295

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 35.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
35.0 / 35.0