Submission #18298646

---

Source Code Expand

#include <iostream>
#include <vector>
#include <set>
#include <map>

using namespace std;

static map<int, set<int>> m;
static set<int> s;

void func(int i, vector<int>& P) {
  // if (i < 0 || i > N) {
  if (i < 0 ) {
    return;
  }

  // cout << i << endl;
  // if (w >= W) {
  //   return;
  // }

  set<int> prev = m[i+1];

  for (auto it = prev.begin(); it != prev.end(); it++) {
    int a = *it;
    int b = *it - P[i];
    if (m.find(i) == m.end()) {
      set<int> scores;
      scores.insert(a);
      scores.insert(b);
      m[i] = scores;
    } else {
      m[i].insert(a);
      m[i].insert(b);
    }

    s.insert(a);
    s.insert(b);
  }

  func(i-1, P);

  return ;
}

int main() {
  int N;
  cin >> N;

  vector<int> P(N);

  int total = 0;
  for (int i = 0; i < N; i++) {
    int p;
    cin >> p;
    P[i] = p;
    total += p;
  }

  set<int> seed;
  seed.insert(total);
  m[N] = seed;
  func(N-1, P);

  cout << s.size() << endl;

  return 0;
}

Submission Info

Judge Result