Submission #18297590


Source Code Expand

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

using namespace std;

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

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

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

  int cached = 0;
  if (m.find(i) != m.end()) {
    cached = m[i];
  }

  if (s.find(w) == s.end()) {
    cached += 1;
    s.insert(w);
  }
  int _w = w + P[i];
  if (s.find(_w) == s.end()) {
    cached += 1;
    s.insert(_w);
  }

  m[i] = cached;

  func(i+1, _w, N, P);
  func(i+1, w, N, P);

  return ;
}

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

  vector<int> P(N);

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

  func(0, 0, N-1, P);

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

  return 0;
}

Submission Info

Submission Time
Task A - コンテスト
User shtvyhr
Language C++ (Clang 10.0.0)
Score 0
Code Size 851 Byte
Status TLE
Exec Time 2205 ms
Memory 3084 KB

Judge Result

Set Name All
Score / Max Score 0 / 2
Status
AC × 3
TLE × 2
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 AC 6 ms 3084 KB
01 TLE 2205 ms 2916 KB
02 TLE 2205 ms 2768 KB
90 AC 9 ms 3000 KB
91 AC 2 ms 3068 KB