Submission #19677032


Source Code Expand

Copy
#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;
}
//----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
set<ll> dp[105][10005][2];
vll v;   ll n;
set<ll> recur(ll i,ll sum,ll ch){
    if(i==n){
        if(ch==0){
           set<ll> s={sum};
          return dp[i][sum][ch]= s; 
        }
        else {
            set<ll> s={sum+v[n-1]};
          return dp[i][sum][ch]= s;   
        }
    }
    if(sz(dp[i][sum][ch])!=0) return dp[i][sum][ch];
    set<ll> a=recur(i+1,sum,0);
      set<ll> b=recur(i+1,sum+v[i],0);

       a.insert(all(b));
      return dp[i][sum][ch]= a;  

}
int main(){
    FAST;
   cin>>n;
    v.resize(n);
    fo(i,0,n)cin>>v[i];
  
 set<ll> a=recur(0,0,1);
 set<ll> b=recur(0,0,0);
  a.insert(all(b));
  cout<<sz(a);

}

Submission Info

Submission Time
Task A - コンテスト
User iamfarraz
Language C++ (GCC 9.2.1)
Score 0
Code Size 2984 Byte
Status WA
Exec Time 2233 ms
Memory 669360 KB

Judge Result

Set Name All
Score / Max Score 0 / 2
Status
WA × 3
TLE × 2
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 WA 82 ms 102484 KB
01 TLE 2233 ms 669360 KB
02 TLE 2233 ms 661404 KB
90 WA 81 ms 101892 KB
91 WA 76 ms 101896 KB