Submission #1244523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244523		warrenn	Bootfall (IZhO17_bootfall)	C++20	100 / 100	215 ms	4440 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;

int dp[250001];
int dp2[250001];
int freq[500002];
int n;
int a[502];

void cek(int idx){
    int tot=0;
    for(int q=1;q<=n;q++){
        tot+=a[q];
    }
    tot-=a[idx];
    for(int q=0;q<=tot+a[idx];q++){
        dp2[q]=dp[q];
    }
    for(int q=a[idx];q<=tot+a[idx];q++){
        dp[q]-=dp[q-a[idx]];
    }

    for(int q=0;q<=tot/2;q++){
        if(dp[q]){
            freq[tot-2*q]++;
        }
    }
    for(int q=0;q<=tot+a[idx];q++){
        dp[q]=dp2[q];
    }
}


int main(){
    cin>>n;
    int tot=0;
    for(int q=1;q<=n;q++){
        cin>>a[q];
        tot+=a[q];
    }
    if(tot%2==1){
        cout<<0<<endl;
        return 0;
    }
    dp[0]=1;
    for(int q=1;q<=n;q++){
        for(int w=tot;w>=a[q];w--){
            dp[w]+=dp[w-a[q]];
        }
    }
  
    if(dp[tot/2]==0){
        cout<<0<<endl;
        return 0;
    }
    for(int q=1;q<=n;q++){
        cek(q);
    }
    int ans=0;
    vector<int>isi;
    for(int q=1;q<=500000;q++){
        if(freq[q]==n){
            ans++;
            isi.push_back(q);
        }
    }
    cout<<ans<<endl;
    for(auto r : isi){
        cout<<r<<" ";
    }
    cout<<endl;


}

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