Submission #6419986

---

Source Code Expand

#include <bits/stdc++.h>
#define INF LLONG_MAX
#define Int long long
#define rep(i,n) for(Int i=0; i<n; ++i)
using namespace std;
 
template<class T> inline bool chmin(T& a, T b) { if(a>b) {a=b; return true;} return false;}
template<class T> inline bool chmas(T& a, T b) { if(a<b) {a=b; return true;} return false;}

int main() {
  Int N; cin >> N;
  vector<Int> p(N);
  Int sum=0;
  rep(i,N) { cin >> p[i]; sum+= p[i]; }
  vector<vector<bool>> dp(N*2, vector<bool>(sum*2, false));
  dp[0][0] = true;

  for(Int i=0; i<=N; ++i) {
    for(Int j=0; j<=sum; ++j) {
      if(dp[i][j]) {
        dp[i+1][j] = true;
        dp[i+1][j+p[i]] = true;
      }
    }
  }
  #if 0
  for(Int i=0; i<=N; ++i) {
    for(Int j=0; j<=sum; ++j) {
      cout << dp[i][j] << " ";
    }
    cout << endl;
  }
  #endif
  Int cnt = 0;
  rep(i, sum*2) {
    if(dp[N+1][i]) ++cnt;
  }
  cout << cnt << endl;
}

Submission Info

Judge Result