제출 #1128123

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128123		icecream	Bootfall (IZhO17_bootfall)	C++20	28 / 100	1107 ms	240680 KiB

bootfall

//                                                             アイスクリーム                                                   
#include <bits/stdc++.h>
#ifndef alks
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#endif
#pragma GCC optimize("O3,unroll-loops")
#define ll long long
#define int ll
#define Yes cout<<"YES\n"; return;
#define No cout<<"NO\n"; return;
#define yes cout<<"Yes\n"; return;
#define no cout<<"No\n"; return;
#define wrans cout<<"-1\n"; return;
using namespace std;
const int N=250505;
const int M=1e6+100;
const int mod1=998244353;
const int mod=1e9+7;
const int INF=1e18;
const long double eps=1e-12;
const string ab="abcdefghijklmnopqrstuvwxyz";
const string AB="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int n;
int a[(int)555];
int dp[N];
int dp1[N];
map <pair<int,int>, int> m;
void alikosh(){
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    dp[0]=dp1[0]=1;
    for(int i=1;i<=n;i++){
        for(int s=sum;s>=a[i];s--){
            dp[s]+=dp[s-a[i]];
            dp1[s]=dp[s];
        }
    }
    vector <int> ans;
    for(int i=1;i<=n;i++){
        for(int s=0;s<=sum-a[i];s++){
            if(dp1[s] && dp1[s+a[i]]){
                dp1[s+a[i]]-=dp1[s];
            }
        }
        for(int s=0;s<=sum;s++){
            if(dp1[s]){
                m[{s,i}]=1;
            }
            dp1[s]=dp[s];
        }
    }
    for(int x=1+1-(a[1] & 1);x<=sum;x+=2){
        bool ok=0;
        for(int i=1;i<=n;i++){
            int y=sum+x-a[i];
            if(y & 1){
                ok=1;
                break;
            }
            if(m[{(sum-a[i]+x)/2-x,i}]<=0){
                ok=1;
                break;
            }
        }
        if(!ok){
            ans.push_back(x);
        }
    }
    if(dp[sum/2]==0){
        cout<<"0\n";
        return;
    }
    cout<<ans.size()<<"\n";
    for(int i:ans){
        cout<<i<<' ';
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int alikosh1=1;
    // cin>>alikosh1; 
    for(int i=1;i<=alikosh1;i++){
        // cout<<"Case "<<i<<": ";
        alikosh();
    }
}
//, Ice \ \ 

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