Submission #88515

#	Time	Username	Problem	Language	Result	Execution time	Memory
88515		Bodo171	Bootfall (IZhO17_bootfall)	C++14	100 / 100	268 ms	5132 KiB

bootfall

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=505;
vector<int> ans;
int dp[nmax*nmax],act[nmax*nmax],cate[nmax*nmax],ok[nmax*nmax];
int a[nmax];
int n,i,j,S,sum;
void add(int &a,int b,int mod)
{
    a+=b;
    if(a>=mod)
        a-=mod;
}
void sub(int &a,int b,int mod)
{
    a-=b;
    if(a<0)
        a+=mod;
}
void solve(int mod)
{
    dp[0]=1;
    for(i=1;i<=sum;i++)
        dp[i]=0,cate[i]=0;
    for(i=1;i<=n;i++)
      for(j=sum/2-a[i];j>=0;j--)
         add(dp[j+a[i]],dp[j],mod);
    for(i=1;i<=n;i++)
    {
        for(j=sum/2;j>=0;j--)
            act[j]=dp[j];
        for(j=0;j<=sum/2-a[i];j++)
            sub(act[j+a[i]],act[j],mod);
        S=sum-a[i];
        for(j=0;j<=S/2;j++)
            if(act[j])
                cate[S-2*j]++;
    }
    for(i=1;i<=sum;i++)
        if(cate[i]==n)
            ok[i]=1;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i],sum+=a[i];
    solve(1000*1000*1000+7);
    if(dp[sum/2]==0||sum%2)
    {
        cout<<"0";
        return 0;
    }
    for(i=1;i<=sum;i++)
        if(ok[i])
         ans.push_back(i);
    cout<<ans.size()<<'\n';
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<' ';
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ans.size();i++)
                 ~^~~~~~~~~~~

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