Submission #566470

#	Time	Username	Problem	Language	Result	Execution time	Memory
566470		birthdaycake	Bootfall (IZhO17_bootfall)	C++17	100 / 100	953 ms	5764 KiB

bootfall

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
 
 
 

int a[200001],dp[2000001],cnt[2000001];
int sum = 0;

void rem(int x){
    for(int i = x; i <= sum; i++){
        dp[i] -= dp[i - x];
        dp[i] += mod;
        dp[i] %= mod;
    }
}


void put(int x){
    for(int i = sum; i >= x; i--){
        dp[i] += dp[i- x];
        dp[i] %= mod;
    }
}


signed main(){
    boost;
    
    
    
    int n; cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    dp[0] = 1;
    for(int i = 0; i < n; i++){
        for(int k = sum; k >= 1; k--){
            if(k - a[i] >= 0){
                dp[k] += dp[k - a[i]];
                dp[k] %= mod;
            }
        }
    }
    if(sum % 2 || dp[sum / 2] == 0){
        cout << 0;
        return 0;
    }
    vector<int>ans;
    for(int i = 0; i < n; i++){
        rem(a[i]);
        sum -= a[i];
        for(int j = 0; j <= sum; j++){
            if(dp[j]){
                int other = sum - j;
                if(other - j <= 0) continue;
                cnt[other - j]++;
                if(cnt[other - j] == n) ans.push_back(other - j);
            }
        }
        put(a[i]);
        sum += a[i];
    }
    sort(ans.begin(),ans.end());
    cout << ans.size() << endl;
    for(auto s:ans) cout << s << ' ' ;
    
    
    
    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