Submission #566540

#	Time	Username	Problem	Language	Result	Execution time	Memory
566540		milisav	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1039 ms	3196 KiB

bootfall

        #include"bits/stdc++.h"
        using namespace std;
        #include <ext/pb_ds/assoc_container.hpp>
        #include <ext/pb_ds/tree_policy.hpp>
        using namespace __gnu_pbds;
        template<class x>
        using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
        //bool plc[600000];
        const int mod=1e9+7;
        int occ[350000];
        int good[350006],a[505],maxn;
        int main()
        {
            ios_base::sync_with_stdio(0);
            cin.tie(0);
            int n,sum=0;
            cin>>n;
            for(int i=0;i<n;i++)
            {
                cin>>a[i];
                sum+=a[i];
            }
            maxn=sum;
            sort(a,a+n);
            //reverse(a,a+n);
            //plc[0]=true;
            vector <int> h;
            occ[0]=1;
            //yes.push_back(0);
            for(int i=0;i<n;i++)
            {
                for(int j=maxn;j>=a[i];j--)
                {
                    occ[j]+=occ[j-a[i]];
                    while(occ[j]>mod)
                        occ[j]-=mod;
                }
            }
            
            //cout<<"HI"<<endl;
            if(occ[sum/2]!=0&&sum%2==0)
            {
                for(int k=0;k<n;k++)
                {
                    sum-=a[k];
                    for(int i=a[k];i<=maxn;i++)
                    {
                        if(occ[i-a[k]]!=0){
                        occ[i]-=occ[i-a[k]];
                        if(occ[i]<0)
                            occ[i]+=mod;
                        
                        }
                    }
                    /*for(int i=0;i<=15;i++)
                    {
                        cout<<occ[i]<<" ";
                    }
                    cout<<"\n";*/
                    //cout<<"HELLO"<<endl;
                    for(int i=0;i<=sum;i++)
                    {
                        int oth=i-(sum-i);
                        if(oth<=0||oth>=maxn)
                            continue;
                        if(occ[i]!=0){
                            good[oth]++;
                            //cout<<oth<<" ";
                            //cout<<oth<<" ";
                        }
                    }
                    for(int i=maxn;i>=a[k];i--)
                    {
                        if(occ[i-a[k]]!=0){
                        occ[i]+=occ[i-a[k]];
                        while(occ[i]>mod)
                            occ[i]-=mod;
                        }
                    }
                    //cout<<endl;
                    sum+=a[k];
                }
                
            }
            for(int i=1;i<=maxn;i++)
                {
         
                        if(good[i]==n){
                            //cout<<"???"<<endl;
                            h.push_back(i);
                }
            }
            cout<<h.size()<<"\n";
            for(auto i : h)
                cout<<i<<" ";
        }

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