Submission #522709

#	Time	Username	Problem	Language	Result	Execution time	Memory
522709		dostigator	Bootfall (IZhO17_bootfall)	C++17	100 / 100	334 ms	3452 KiB

bootfall

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
#define IShowSpeed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define popcnt __builtin_popcount
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define mii map<int,int>
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define pb push_back
#define vt vector
#define endl '\n'
#define X first
#define Y second
typedef long double ld;
typedef long long ll;
const ll dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},N=1e6;
const ll mod=1e9+7,inf=1e18;
int dp[N];
int used[N];
void solve(){
    int n;
    cin>>n;
    int a[n+2],sum=0;
    for(int i=1; i<=n; ++i) {cin>>a[i];sum+=a[i];}
    dp[0]=1;
    for(int j=1; j<=n; ++j) for(int i=sum; i>=a[j]; --i) dp[i]+=dp[i-a[j]];
    if(!dp[sum/2] || sum%2){
        cout<<0<<endl;
        return;
    }
    vt<int>res;
    for(int i=1; i<=n; ++i){
        for(int j=a[i]; j<=sum; ++j) dp[j]-=dp[j-a[i]];
        for(int nd=1; nd<=sum; ++nd){
            int h=sum-a[i];
            h+=nd;
            if(h%2 || !dp[h/2]) continue;
            used[nd]++;
            if(used[nd]==n)res.pb(nd);
        }
        for(int j=sum; j>=a[i]; --j) dp[j]+=dp[j-a[i]];
    }
    cout<<res.size()<<endl;
    for(int x:res)cout<<x<<' ';
}
int main() {
    IShowSpeed;
    int tt=1;
    //cin>>tt;
    while(tt--) solve();
}

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