제출 #1131303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131303		Pishka12	Bootfall (IZhO17_bootfall)	C++20	28 / 100	1095 ms	3440 KiB

bootfall

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

int main()
{
    ll n;
    cin>>n;
    vector<ll> a(n+1);
    ll sum = 0;
    for (int i = 1;i<=n;i++) {
        cin>>a[i];
        sum += a[i];
    }
    if (sum%2 != 0){
        cout<<0<<endl;
        return 0;
    }
    bitset<250000+1> dp;
    dp[0] = true;
    for (int i = 1;i<=n;i++) {
        dp |= dp<<a[i];
    }
    if (!dp[sum/2]) {
        cout<<0<<endl;
        return 0;
    }
    set<ll> ans;
    for (int i = 1;i<=sum;i++) {
        ans.insert(i);
    }
    for (int i = 1;i<=n;i++) {
        bitset<250000+1> fe;
        fe[0] = true;
        for (int j = 1;j<=n;j++) {
            if (j != i) {
                fe |= fe<<a[j];
            }
        }
        set<ll> co;
        ll resu = sum - a[i];
        for (ll z = 1;z<fe.size();z++) {
            if (fe[z]) {
                ll de = abs(2*z - resu);
                if(ans.find(de) != ans.end()) {
                    co.insert(de);
                }
            }
        }
        ans = co;
    }
    cout<<ans.size()<<endl;
    for (auto e : ans) {
        cout<<e<<' ';
     }
    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