제출 #1183302

#제출 시각아이디문제언어결과실행 시간메모리
1183302AlgorithmWarriorBootfall (IZhO17_bootfall)C++20
65 / 100
1096 ms5252 KiB
#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];

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

void delete_knapsack(int nr){
    int i;
    for(i=0;i<2*ORIG;++i)
        vechi[i]=nou[i];
    for(i=2*nr;i<2*ORIG;++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)
        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()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    init();
    solve();
    write();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...