Submission #579821

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
579821	2022-06-20T02:56:17 Z	gg123_pe	Bootfall (IZhO17_bootfall)	C++14	28 / 100	26 ms	464 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; 
const ll mod = 1e9 + 7; 


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

void add(int x){
    fa(i,s,x) {
        dp[i] = (dp[i] + dp[i-x]) % 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;
        }
    
      	if(on.count() == 0){
          cout << "0\n"; 
        return 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 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	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 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	212 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 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	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 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	212 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	340 KB	Output is correct
22	Correct	3 ms	340 KB	Output is correct
23	Correct	2 ms	212 KB	Output is correct
24	Correct	4 ms	340 KB	Output is correct
25	Correct	6 ms	340 KB	Output is correct
26	Correct	6 ms	340 KB	Output is correct
27	Correct	8 ms	376 KB	Output is correct
28	Correct	7 ms	340 KB	Output is correct
29	Correct	7 ms	384 KB	Output is correct
30	Correct	2 ms	340 KB	Output is correct
31	Correct	5 ms	340 KB	Output is correct
32	Correct	4 ms	340 KB	Output is correct
33	Correct	7 ms	392 KB	Output is correct
34	Correct	8 ms	340 KB	Output is correct
35	Correct	9 ms	340 KB	Output is correct
36	Correct	5 ms	340 KB	Output is correct

Subtask #4
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 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	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 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	212 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	340 KB	Output is correct
22	Correct	3 ms	340 KB	Output is correct
23	Correct	2 ms	212 KB	Output is correct
24	Correct	4 ms	340 KB	Output is correct
25	Correct	6 ms	340 KB	Output is correct
26	Correct	6 ms	340 KB	Output is correct
27	Correct	8 ms	376 KB	Output is correct
28	Correct	7 ms	340 KB	Output is correct
29	Correct	7 ms	384 KB	Output is correct
30	Correct	2 ms	340 KB	Output is correct
31	Correct	5 ms	340 KB	Output is correct
32	Correct	4 ms	340 KB	Output is correct
33	Correct	7 ms	392 KB	Output is correct
34	Correct	8 ms	340 KB	Output is correct
35	Correct	9 ms	340 KB	Output is correct
36	Correct	5 ms	340 KB	Output is correct
37	Correct	25 ms	464 KB	Output is correct
38	Correct	26 ms	460 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 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	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 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	212 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	340 KB	Output is correct
22	Correct	3 ms	340 KB	Output is correct
23	Correct	2 ms	212 KB	Output is correct
24	Correct	4 ms	340 KB	Output is correct
25	Correct	6 ms	340 KB	Output is correct
26	Correct	6 ms	340 KB	Output is correct
27	Correct	8 ms	376 KB	Output is correct
28	Correct	7 ms	340 KB	Output is correct
29	Correct	7 ms	384 KB	Output is correct
30	Correct	2 ms	340 KB	Output is correct
31	Correct	5 ms	340 KB	Output is correct
32	Correct	4 ms	340 KB	Output is correct
33	Correct	7 ms	392 KB	Output is correct
34	Correct	8 ms	340 KB	Output is correct
35	Correct	9 ms	340 KB	Output is correct
36	Correct	5 ms	340 KB	Output is correct
37	Correct	25 ms	464 KB	Output is correct
38	Correct	26 ms	460 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 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	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 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	212 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	340 KB	Output is correct
22	Correct	3 ms	340 KB	Output is correct
23	Correct	2 ms	212 KB	Output is correct
24	Correct	4 ms	340 KB	Output is correct
25	Correct	6 ms	340 KB	Output is correct
26	Correct	6 ms	340 KB	Output is correct
27	Correct	8 ms	376 KB	Output is correct
28	Correct	7 ms	340 KB	Output is correct
29	Correct	7 ms	384 KB	Output is correct
30	Correct	2 ms	340 KB	Output is correct
31	Correct	5 ms	340 KB	Output is correct
32	Correct	4 ms	340 KB	Output is correct
33	Correct	7 ms	392 KB	Output is correct
34	Correct	8 ms	340 KB	Output is correct
35	Correct	9 ms	340 KB	Output is correct
36	Correct	5 ms	340 KB	Output is correct
37	Correct	25 ms	464 KB	Output is correct
38	Correct	26 ms	460 KB	Output is correct
39	Runtime error	1 ms	340 KB	Execution killed with signal 11
40	Halted	0 ms	0 KB	-

Submission #579821

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