Submission #566539

#	Time	Username	Problem	Language	Result	Execution time	Memory
566539		milisav	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1082 ms	3128 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[2500000];
    int good[2500006],a[5005],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