提出 #18297590


ソースコード 拡げる

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;
}

提出情報

提出日時
問題 A - コンテスト
ユーザ shtvyhr
言語 C++ (Clang 10.0.0)
得点 0
コード長 851 Byte
結果 TLE
実行時間 2205 ms
メモリ 3084 KB

ジャッジ結果

セット名 All
得点 / 配点 0 / 2
結果
AC × 3
TLE × 2
セット名 テストケース
All 00, 01, 02, 90, 91
ケース名 結果 実行時間 メモリ
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