Submission #1297131

#TimeUsernameProblemLanguageResultExecution timeMemory
1297131jahongirBootfall (IZhO17_bootfall)C++20
100 / 100
217 ms4048 KiB
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,
					 tree_order_statistics_node_update>;
 
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()



const int mxn = 500;
int arr[mxn+1];
ll dp[mxn*mxn+1];
short res[mxn*mxn+1];

void solve(){
    int n; cin >> n;
    dp[0] = 1;
    int sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        for(int j = sum; j >= 0; j--)
            dp[j+arr[i]] += dp[j];
        sum += arr[i];
    }

    if(sum%2 || dp[sum/2]==0){
        cout << 0; return;
    }


    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= sum-arr[i]; j++)
            dp[j+arr[i]] -= dp[j];
        
        for(int j = (sum-arr[i])/2; j >= 0; j--){
            if(dp[j] && dp[sum-arr[i]-j])
                res[sum-arr[i]-2*j]++;
            
        }
        
        for(int j = sum-arr[i]; j >= 0; j--)
            dp[j+arr[i]] += dp[j];
    }

    vector<int> vec;
    for(int i = 1; i <= sum; i++) if(res[i]==n) vec.push_back(i);
    cout << vec.size() << '\n';

    for(auto x : vec) cout << x << ' ';
}


signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--){solve();}
}
#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...