Submission #19677528

---

Source Code Expand

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define endl "\n"
#define vll vector<ll>
#define pll pair<ll,ll>
#define pqb priority_queue<ll>
#define pqs priority_queue<ll,vll,greater<ll> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x)             (int)((x).size())
#define FAST ios_base :: sync_with_stdio (false); cin.tie (NULL)
#define fo(i,s,n) for(ll i=s;i<n;i++)
#define rfo(i,n,s) for(ll i=n;i>=s;i--)
using namespace std;
typedef long long int ll;
//------------------------------MOD-Operations--------------------------------------------------------------------------------------------------------------------------------------------//
const ll M = 1e9 + 7;
const ll N = 2e5 + 5;
const ll inf = 9e18;
ll mod(ll x){   return (x%M);}
ll ml(ll a,ll b){  return mod(mod(a)*mod(b));}
ll power(ll a,ll n){   if(n==0) return 1;   else if(n==1) return a;   ll R=power(a,n/2)%M;    if(n%2==0) {    return mod(ml(R,R));  }   else {   return mod(ml(ml(R,a),mod(R)));  }  }
ll mod_inv(ll n){  return power(n,M-2);}
// only if M is prime
ll mod_div(ll a,ll b){   ll ans=mod(a);   ll b1=power(b,M-2);    ans= mod(ml(ans,b1));     return ans;   }
ll C(ll n,  ll r) 
{   if(r > n || n < 0 || r < 0)return 0;
 if (r == 0) 
        return 1; 
   ll nfc=1,rfc=1,nrfc=1;
    for (int i = 1; i <= n; i++) 
      { 
           nfc=ml(nfc,i);
           if(i==r){rfc=nfc;}
           if(i==(n-r)){nrfc=nfc;} 
     } 
    return ml(ml(nfc,mod_inv(rfc)),mod_inv(nrfc)); 
} 
vector<ll> seive(ll n){
    vector<ll> isprime(n+1,true); 
    isprime[0]=false;
    isprime[1]=false;//kyuki 1 prime nhi hota
    for( ll i=2;i<sqrt(n);i++){
        if(isprime[i]){
            for(int j=i*i;j<=n;j+=i){
                isprime[j]=false;
            }
        }
    }
    vll allp;
    fo(i,2,n+1)if(isprime[i])allp.pb(i);
return allp;
}
//----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ll dp[105][10005][2];
vll v;   ll n;
 set<ll> s;

ll recur(ll i,ll sum,ll ch){
    if(i==n){
         s.insert(sum);      
      return dp[i][sum][ch]=sz(s); 
    }
    if(dp[i][sum][ch]!=-1) return dp[i][sum][ch];
recur(i+1,sum,0);
recur(i+1,sum+v[i],1);

    return dp[i][sum][ch]=sz(s);
    
}
int main(){
    FAST;
   cin>>n;
    v.resize(n);
    fo(i,0,n)cin>>v[i];

    fo(i,0,105){
    fo(j,0,10005){
        fo(k,0,2){
            dp[i][j][k]=-1;
        }
    }
}
    recur(0,0,0);
  

    cout<<sz(s);


}

Submission Info

Judge Result