Submission #566225

#	Time	Username	Problem	Language	Result	Execution time	Memory
566225		MrDeboo	Bootfall (IZhO17_bootfall)	C++17	28 / 100	1090 ms	832 KiB

bootfall

#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    int arr[n];
    for(auto &i:arr)cin>>i;
    vector<bool>v(500*n+1);
    v[0]=1;
    int sm=0;
    for(int i=0;i<n;i++){
        sm+=arr[i];
        for(int w=500*n;w>=0;w--){
            if(v[w])v[w+arr[i]]=1;
        }
    }
    if(sm%2!=0||!v[sm/2]){cout<<0;return 0;}
    sm++;
    vector<int>ans(sm);
    for(int i=0;i<n;i++){
        vector<bool>vec(sm);
        vec[0]=1;
        int smm=0;
        for(int w=0;w<n;w++){
            if(w==i)continue;
            smm+=arr[w];
            for(int j=sm;j>=0;j--){
                if(vec[j])vec[j+arr[w]]=1;
            }
        }
        set<int>st;
        for(int w=0;w<=sm;w++){
            if(vec[w])st.insert(abs(smm-w-w));
        }
        for(auto &w:st)ans[w]++;
    }
    int cnt=0;
    for(auto &i:ans){
        if(i==n)cnt++;
    }
    cout<<cnt<<endl;
    for(int i=1;i<=sm;i++){
        if(ans[i]==n)cout<<i<<' ';
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35