Submission #566543

#	Time	Username	Problem	Language	Result	Execution time	Memory
566543		milisav	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1084 ms	3224 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=sum/2;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