Submission #1183309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183309		AlgorithmWarrior	Bootfall (IZhO17_bootfall)	C++20	100 / 100	909 ms	5724 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

int const MOD=1000000007;
int const ORIG=251005;
int const MAX=505;
int nou[2*ORIG];
int vechi[2*ORIG];
int n;
int v[MAX];
vector<int>ans;
bool sol[ORIG];
int sum;

void add_knapsack(int nr){
    int i;
    for(i=ORIG-sum;i<=ORIG+sum;++i)
        vechi[i]=nou[i];
    for(i=ORIG-sum;i<=ORIG+sum;++i)
        nou[i]=(vechi[i-nr]+vechi[i+nr])%MOD;
}

void delete_knapsack(int nr){
    int i;
    for(i=ORIG-sum;i<=ORIG+sum;++i)
        vechi[i]=nou[i];
    for(i=ORIG-sum;i<=ORIG+sum;++i)
        nou[i]=(vechi[i-nr]-nou[i-2*nr]+MOD)%MOD;
}

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
}

void init(){
    nou[ORIG]=1;
    int i;
    for(i=1;i<=n;++i){
        sum+=v[i];
        add_knapsack(v[i]);
    }
}

void solve(){
    if(!nou[ORIG])
        return;
    int i,j;
    for(i=0;i<ORIG;++i)
        sol[i]=1;
    for(i=1;i<=n;++i){
        delete_knapsack(v[i]);
        for(j=0;j<ORIG;++j)
            sol[j]&=(nou[ORIG-j] || nou[ORIG+j]);
        add_knapsack(v[i]);
    }
    for(i=0;i<ORIG;++i)
        if(sol[i])
            ans.push_back(i);
}

void write(){
    cout<<ans.size()<<'\n';
    for(auto val : ans)
        cout<<val<<' ';
}

int main()
{
    read();
    init();
    solve();
    write();
    return 0;
}

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