Submission #566288

#	Time	Username	Problem	Language	Result	Execution time	Memory
566288		birthdaycake	Bootfall (IZhO17_bootfall)	C++17	28 / 100	873 ms	1996 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[20001];
signed main(){
    boost;
    
    
    
    int n,  sum = 0; cin >> n;
    
    map<int,int>o;
    
    
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    for(int i = 0; i < n; i++){
        vector<int>x;
        map<int,int>freq;
        
        
        sum -= a[i];
        
        for(int j = 1; j <= 10000; j++) dp[j] = 0;
        
        for(int j = 0; j < n; j++){
            if(i != j) x.push_back(a[j]);
        }
        dp[0] = 1;
        for(int j = 0; j < n - 1; j++){
            for(int k = 10000; k >= 1; k--){
                if(k - x[j] >= 0) {
                    dp[k] += dp[k - x[j]];
                }
            }
            
            
        }
        //cout << sum << ' ' << i << endl;
        for(int j = 1; j <= sum; j++){
            if(dp[j]){
                int x = abs(j - sum);
                
                freq[abs(x - j)]++;
                //cout <<  abs(x - j) << ' ';
                if(freq[abs(j - x)] == 1){
                    o[abs(j - x)]++;
                }
            }
        }
        //cout << endl;
        sum += a[i];
        
    }
    for(int i = 1; i <= 10000; i++) dp[i] = 0;
    for(int i = 0; i < n; i++){
        for(int k = 10000; k >= 1; k--){
            if(k - a[i] >= 0){
                dp[k] += dp[k - a[i]];
            }
        }
    }
    if(sum % 2 || dp[sum / 2] == 0){
        cout << 0;
        return 0;
    }
    
    
    vector<int>ans;
    for(auto s:o){
        if(s.second == n){
            ans.push_back(s.first);
        }
    }
    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: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35