Submission #5499051

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define ld long double
#define fast ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL)
#define F(i,a,b) for(int i= (int)(a); i<(int)(b);i++)
#define FI(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define what_is(x) cerr << #x << " is " << x << endl;
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pii pair<int,int>
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define mp make_pair
#define ff first
#define ss second
#define MOD 1000000007
const int N = 1e5+7 ;
string s ;
int main(){fast ;
	int n,k ;
	cin >> n ;
	vector<int> p(n) ;
	for(int& i : p)
		cin >> i ; 
	vector<vector<int>> dp(n+1,vector<int>(10100)) ;
	// dp[i][j] is 1  on including i th element from p and sum j is possible  
	dp[0][0] = 1 ; // no element no sum 
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < 10100; j++){
			if(dp[i][j]){
				dp[i+1][j] = 1 ; // with each element included , prev sum is possible
				dp[i+1][j+p[i]] = 1 ; // from cur sum j sum j+p[i] is possible 
			}
		}
	}
	// all n elements are included 
	int ans = 0 ;
	for(int j = 0 ; j < 10100 ; j++){
		if(dp[n][j])
			ans++ ;
	}
	cout << ans << endl ;
}

Submission Info

Judge Result