Submission #906029

#	Time	Username	Problem	Language	Result	Execution time	Memory
906029		stefanneagu	Detecting Molecules (IOI16_molecules)	C++17	31 / 100	1024 ms	58348 KiB

molecules

#include <bits/stdc++.h>
#include "molecules.h"

using namespace std;

const int nmax = 1e5;

bitset<nmax> ans[nmax];
bitset<nmax> f;

std::vector<int> find_subset(int vmin, int vmax, std::vector<int> de_ce_de_la_zero) {
  int n = de_ce_de_la_zero.size();
  vector<int> v;
  v.push_back(0);
  for(auto it : de_ce_de_la_zero) {
    v.push_back(it);
  }
  f[0] = 1;
  for(int i = 1; i <= n; i ++) {
    for(int sum = vmax - v[i]; sum >= 0; sum --) {
      if(f[sum]) {
        f[sum + v[i]] = 1;
        ans[sum + v[i]] = ans[sum];
        ans[sum + v[i]][i] = 1;
      }
    }
  }
  for(int i = vmin; i <= vmax; i ++) {
    if(f[i]) {
      vector<int> r;
      for(int j = 1; j <= n; j ++) {
        if(ans[i][j]) {
          r.push_back(j - 1);
        }
      }
      return r;
    }
  }
  vector<int> skill_issue;
  return skill_issue;
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31