Submission #39847

#	Time	Username	Problem	Language	Result	Execution time	Memory
39847		igzi	Bootfall (IZhO17_bootfall)	C++14	28 / 100	1000 ms	128064 KiB

bootfall

#include <bits/stdc++.h>
#define maxN 505
#define maxA 505

using namespace std;
bool b[maxN][maxN*maxA];
int n,i,j,s=0,a[maxN];
vector <int> v,ans;
bool moze(int x){
for(int i=0;i<n;i++){
    if((s+x-a[i])%2 || !b[i][(s+x-a[i])/2]) return false;
}
return true;
}

int main()
{
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a[i];
        s+=a[i];
    }
    for(j=0;j<=n;j++){
    for(i=1;i<=250000;i++){
        b[j][i]=false;
    }}
    for(j=0;j<=n;j++){
    b[j][0]=false;
    v.push_back(0);
    for(i=0;i<n;i++){
        int t,k;
        if(i==j) continue;
        t=v.size();
        for(k=0;k<t;k++){
            if(!b[j][a[i]+v[k]]){
                b[j][a[i]+v[k]]=true;
                v.push_back(a[i]+v[k]);
            }
        }
    }
    v.clear();
    }
    if(s%2 || !b[n][s/2]) cout<<0<<endl;
    else{
        for(i=0;i<=250000;i++){
            if(moze(i)) ans.push_back(i);
        }
        cout<<ans.size()<<endl;
        for(i=0;i<ans.size();i++){
            cout<<ans[i]<<" ";
        }
    }
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<ans.size();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