Submission #5888838

---

Source Code Expand

#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

template<typename T>
bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}

template<typename T>
bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

int dp[110][10100];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N=in();
	vector<int> A(N);
	REP(i,N){
		A[i]=in();
	}
	int sum = accumulate(ALL(A),0);
	dp[0][0] = 1;

	for(int i=0;i<N;i++){
		for(int k=0;k<10100;k++){
			if(dp[i][k]==1 && k+A[i]<10100) chmax(dp[i+1][k+A[i]],1);
			chmax(dp[i+1][k],dp[i][k]);
		}
	}

	cout << count(dp[N],dp[N]+sum+1,1) << endl;
	return 0;
}

Submission Info

Judge Result