Submission #499717

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
499717	2021-12-29T10:11:17 Z	Ronin13	Bootfall (IZhO17_bootfall)	C++14	28 / 100	629 ms	5188 KB

bootfall

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 1e9+1
#define linf 1e18+1
using namespace std;

bool dp[101][250001];

void solve(){
    int n;cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++)cin>>a[i];
    int mx=0;
    for(int i=1;i<=n;i++){
        mx=max(mx,a[i]);
    }
    mx*=n;
    for(int i=0;i<=n;i++){
        dp[i][0]=true;
        for(int j=1;j<=n;j++){
            if(j==i)continue;
            for(int x=mx;x>=0;x--){
                if(x-a[j]>=0&&dp[i][x-a[j]])dp[i][x]=true;
            }
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
        sum+=a[i];
    vector<int>ans;
    if(!dp[0][sum/2]){
        cout<<0;
        return;
    }
    for(int i=1;i<=sum;i++){

        bool ind=true;

        for(int j=1;j<=n;j++){
            int x=sum+i;
            x-=a[j];
            if(x&1){
                ind=false;break;
            }
            ind&=dp[j][x/2];
        }
        if(ind)ans.pb(i);
    }
    cout<<ans.size()<<"\n";
    for(int to:ans)cout<<to<<" ";
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int test=1;//cin>>test;
    while(test--)solve();
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	1 ms	448 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	448 KB	Output is correct
16	Correct	1 ms	448 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	460 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	1 ms	448 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	448 KB	Output is correct
16	Correct	1 ms	448 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	460 KB	Output is correct
21	Correct	28 ms	812 KB	Output is correct
22	Correct	42 ms	888 KB	Output is correct
23	Correct	14 ms	688 KB	Output is correct
24	Correct	81 ms	1084 KB	Output is correct
25	Correct	100 ms	1524 KB	Output is correct
26	Correct	111 ms	1732 KB	Output is correct
27	Correct	116 ms	1632 KB	Output is correct
28	Correct	116 ms	1644 KB	Output is correct
29	Correct	112 ms	1604 KB	Output is correct
30	Correct	103 ms	1260 KB	Output is correct
31	Correct	110 ms	1452 KB	Output is correct
32	Correct	107 ms	1220 KB	Output is correct
33	Correct	105 ms	1732 KB	Output is correct
34	Correct	106 ms	1688 KB	Output is correct
35	Correct	116 ms	1620 KB	Output is correct
36	Correct	103 ms	1156 KB	Output is correct

Subtask #4
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	1 ms	448 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	448 KB	Output is correct
16	Correct	1 ms	448 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	460 KB	Output is correct
21	Correct	28 ms	812 KB	Output is correct
22	Correct	42 ms	888 KB	Output is correct
23	Correct	14 ms	688 KB	Output is correct
24	Correct	81 ms	1084 KB	Output is correct
25	Correct	100 ms	1524 KB	Output is correct
26	Correct	111 ms	1732 KB	Output is correct
27	Correct	116 ms	1632 KB	Output is correct
28	Correct	116 ms	1644 KB	Output is correct
29	Correct	112 ms	1604 KB	Output is correct
30	Correct	103 ms	1260 KB	Output is correct
31	Correct	110 ms	1452 KB	Output is correct
32	Correct	107 ms	1220 KB	Output is correct
33	Correct	105 ms	1732 KB	Output is correct
34	Correct	106 ms	1688 KB	Output is correct
35	Correct	116 ms	1620 KB	Output is correct
36	Correct	103 ms	1156 KB	Output is correct
37	Runtime error	629 ms	5188 KB	Execution killed with signal 11
38	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	1 ms	448 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	448 KB	Output is correct
16	Correct	1 ms	448 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	460 KB	Output is correct
21	Correct	28 ms	812 KB	Output is correct
22	Correct	42 ms	888 KB	Output is correct
23	Correct	14 ms	688 KB	Output is correct
24	Correct	81 ms	1084 KB	Output is correct
25	Correct	100 ms	1524 KB	Output is correct
26	Correct	111 ms	1732 KB	Output is correct
27	Correct	116 ms	1632 KB	Output is correct
28	Correct	116 ms	1644 KB	Output is correct
29	Correct	112 ms	1604 KB	Output is correct
30	Correct	103 ms	1260 KB	Output is correct
31	Correct	110 ms	1452 KB	Output is correct
32	Correct	107 ms	1220 KB	Output is correct
33	Correct	105 ms	1732 KB	Output is correct
34	Correct	106 ms	1688 KB	Output is correct
35	Correct	116 ms	1620 KB	Output is correct
36	Correct	103 ms	1156 KB	Output is correct
37	Runtime error	629 ms	5188 KB	Execution killed with signal 11
38	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	460 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	1 ms	448 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	448 KB	Output is correct
16	Correct	1 ms	448 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	460 KB	Output is correct
21	Correct	28 ms	812 KB	Output is correct
22	Correct	42 ms	888 KB	Output is correct
23	Correct	14 ms	688 KB	Output is correct
24	Correct	81 ms	1084 KB	Output is correct
25	Correct	100 ms	1524 KB	Output is correct
26	Correct	111 ms	1732 KB	Output is correct
27	Correct	116 ms	1632 KB	Output is correct
28	Correct	116 ms	1644 KB	Output is correct
29	Correct	112 ms	1604 KB	Output is correct
30	Correct	103 ms	1260 KB	Output is correct
31	Correct	110 ms	1452 KB	Output is correct
32	Correct	107 ms	1220 KB	Output is correct
33	Correct	105 ms	1732 KB	Output is correct
34	Correct	106 ms	1688 KB	Output is correct
35	Correct	116 ms	1620 KB	Output is correct
36	Correct	103 ms	1156 KB	Output is correct
37	Runtime error	629 ms	5188 KB	Execution killed with signal 11
38	Halted	0 ms	0 KB	-

Submission #499717

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