Submission #579820

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
579820	2022-06-20T02:52:27 Z	gg123_pe	Bootfall (IZhO17_bootfall)	C++14	28 / 100	24 ms	388 KB

bootfall

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

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 1e5 + 5, M = 1e6 + 5, mod = 1e9 + 7; 


int n, s, a[505], dp[25005]; 
bitset <25005> on; 

void add(int x){
    fa(i,s,x) {
        dp[i] += dp[i-x]; 
        dp[i] %= mod; 
    }
}

void res(int x){
    f(i,x,s+1){
        dp[i] = (dp[i] - dp[i-x] + mod) % mod; 
    }
}
int main(){
    cin >> n; 

    f(i,1,n+1) {
        cin >> a[i]; 
        s += a[i]; 
    }

    dp[0] = 1; 

    f(i,1,n+1){
        add(a[i]); 
    }

    if(s&1 or dp[s/2] == 0){
        cout << "0\n"; 
        return 0; 
    }

    f(i,1,s+1) on[i] = 1;       

    f(i,1,n+1){
        res(a[i]); 

        int x = s - a[i]; 
        f(j,1,s+1){
            if(x%2 != j%2 or dp[(x+j)/2] == 0) on[j] = 0;
        }
        add(a[i]); 
    }
    cout << on.count() << "\n";  
    f(i,1,s+1) if(on[i]) cout << i << " "; 
    cout << "\n"; 

    return 0; 
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	224 KB	Output is correct
4	Correct	1 ms	300 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	304 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	224 KB	Output is correct
4	Correct	1 ms	300 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	304 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	304 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	224 KB	Output is correct
4	Correct	1 ms	300 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	304 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	304 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	2 ms	212 KB	Output is correct
22	Correct	2 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	3 ms	212 KB	Output is correct
25	Correct	7 ms	340 KB	Output is correct
26	Correct	8 ms	340 KB	Output is correct
27	Correct	6 ms	300 KB	Output is correct
28	Correct	8 ms	352 KB	Output is correct
29	Correct	8 ms	308 KB	Output is correct
30	Correct	4 ms	212 KB	Output is correct
31	Correct	5 ms	340 KB	Output is correct
32	Correct	4 ms	212 KB	Output is correct
33	Correct	7 ms	344 KB	Output is correct
34	Correct	7 ms	304 KB	Output is correct
35	Correct	7 ms	340 KB	Output is correct
36	Correct	4 ms	344 KB	Output is correct

Subtask #4
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	224 KB	Output is correct
4	Correct	1 ms	300 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	304 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	304 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	2 ms	212 KB	Output is correct
22	Correct	2 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	3 ms	212 KB	Output is correct
25	Correct	7 ms	340 KB	Output is correct
26	Correct	8 ms	340 KB	Output is correct
27	Correct	6 ms	300 KB	Output is correct
28	Correct	8 ms	352 KB	Output is correct
29	Correct	8 ms	308 KB	Output is correct
30	Correct	4 ms	212 KB	Output is correct
31	Correct	5 ms	340 KB	Output is correct
32	Correct	4 ms	212 KB	Output is correct
33	Correct	7 ms	344 KB	Output is correct
34	Correct	7 ms	304 KB	Output is correct
35	Correct	7 ms	340 KB	Output is correct
36	Correct	4 ms	344 KB	Output is correct
37	Correct	23 ms	364 KB	Output is correct
38	Correct	24 ms	388 KB	Output is correct
39	Runtime error	1 ms	340 KB	Execution killed with signal 11
40	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	224 KB	Output is correct
4	Correct	1 ms	300 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	304 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	304 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	2 ms	212 KB	Output is correct
22	Correct	2 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	3 ms	212 KB	Output is correct
25	Correct	7 ms	340 KB	Output is correct
26	Correct	8 ms	340 KB	Output is correct
27	Correct	6 ms	300 KB	Output is correct
28	Correct	8 ms	352 KB	Output is correct
29	Correct	8 ms	308 KB	Output is correct
30	Correct	4 ms	212 KB	Output is correct
31	Correct	5 ms	340 KB	Output is correct
32	Correct	4 ms	212 KB	Output is correct
33	Correct	7 ms	344 KB	Output is correct
34	Correct	7 ms	304 KB	Output is correct
35	Correct	7 ms	340 KB	Output is correct
36	Correct	4 ms	344 KB	Output is correct
37	Correct	23 ms	364 KB	Output is correct
38	Correct	24 ms	388 KB	Output is correct
39	Runtime error	1 ms	340 KB	Execution killed with signal 11
40	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	224 KB	Output is correct
4	Correct	1 ms	300 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	304 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	304 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	2 ms	212 KB	Output is correct
22	Correct	2 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	3 ms	212 KB	Output is correct
25	Correct	7 ms	340 KB	Output is correct
26	Correct	8 ms	340 KB	Output is correct
27	Correct	6 ms	300 KB	Output is correct
28	Correct	8 ms	352 KB	Output is correct
29	Correct	8 ms	308 KB	Output is correct
30	Correct	4 ms	212 KB	Output is correct
31	Correct	5 ms	340 KB	Output is correct
32	Correct	4 ms	212 KB	Output is correct
33	Correct	7 ms	344 KB	Output is correct
34	Correct	7 ms	304 KB	Output is correct
35	Correct	7 ms	340 KB	Output is correct
36	Correct	4 ms	344 KB	Output is correct
37	Correct	23 ms	364 KB	Output is correct
38	Correct	24 ms	388 KB	Output is correct
39	Runtime error	1 ms	340 KB	Execution killed with signal 11
40	Halted	0 ms	0 KB	-

Submission #579820

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 16.0

Subtask #5 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
0 / 16.0

Subtask #5
0 / 21.0

Subtask #6
0 / 35.0