1516C - Baby Ehab Partitions Again - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mod 1000000007
#define ff first
#define se second
#define vc vector
vector <int> primes;
vector <bool> chk(31625,false);
void seive()
{
  for(int i=2;i<=31625;i++)
  {
    if(!chk[i])
    {
      chk[i]=true;
      primes.pb(i);
      for(int j=2*i;j<=31625;j+=i)
      chk[j]=true;
    }
  }
}
ll bpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
        {
            res=res*a;
            res%=mod;
        }
        a=a*a;
        a%=mod;
        b=b>>1;
    }
    return res;
}
ll fact(ll p)
{
	ll ans=1;
	for(ll i=1;i<=p;i++)
	{
		ans*=i;
		ans%=mod;
	}
	return ans;
}
string num(ll n)
{
	string res="";
	while(n)
	{
		ll po=n%10;
		n=n/10;
		res+=to_string(po);
	}
	reverse(res.begin(),res.end());
	return res;
}
bool solve(int ind,int tar,vector<int>a,vector<vector<int>>&dp)
{
    if(tar==0)
    return true;
    if(tar<0)
    return false;
    if(ind==0)
    return (a[0]==tar);
    if(dp[ind][tar]!=-1)
    return dp[ind][tar];
    bool take,notake;
    notake=solve(ind-1,tar,a,dp);
    take=solve(ind-1,tar-a[ind],a,dp);
    return dp[ind][tar]=take|notake;
    
}
int main()
{
		 ll n,i,j;
	    cin>>n;
	    vector<int>a(n);
	    for(i=0;i<n;i++)
	    cin>>a[i];
	    ll su=0;
	    for(i=0;i<n;i++)
	    su+=a[i];
	    if(su%2)
	    cout<<"0"<<"\n";
	    else
	    {
	        vector<vector<int>>dp(n,vector<int>(su/2+1,-1));
	        bool ans=solve(n-1,su/2,a,dp);
	        if(ans==false)
	        cout<<"0"<<"\n";
	        else
	        {
	            int ind=-1;
                int f;
                for(j=1;j<13;j++)
                {
                    f=0;
	            for(i=0;i<n;i++)
	            {
	                if(a[i]%2)
	                {
                        f=1;
	                    ind=i+1;
                        break;
	                    
	                }
	                else
	                {
	                    a[i]/=2;
	                }
	            }
                if(f==1)
                break;
                }
	            cout<<"1"<<"\n";
	            cout<<ind<<"\n";
	            
	        }
	    }
	
}