Submission #200870

#	Time	Username	Problem	Language	Result	Execution time	Memory
200870		oofsauce	Detecting Molecules (IOI16_molecules)	C++14	19 / 100	39 ms	26488 KiB

molecules

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

using namespace std;

int l;
int u;
vector<int> weights;

vector<vector<bool>> visited;
vector<int> ans;

bool recurse(int idx, int w) {
  if(w <= u && w >= l) return true;
  if(idx >= weights.size()) return false;
  if(visited[idx][w]) return false;

  if(recurse(idx+1, w)) return true;
  if(recurse(idx+1, w+weights[idx])) {
    ans.push_back(idx);
    return true;
  }
  visited[idx][w] = true;
  return false;
}

vector<int> find_subset(int l_, int u_, vector<int> weights_) {
  l = l_;
  u = u_;
  weights = weights_;

  visited.resize(10000, vector<bool>(10000,false));

  recurse(0,0);

  return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'bool recurse(int, int)':
molecules.cpp:15:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(idx >= weights.size()) return false;
      ~~~~^~~~~~~~~~~~~~~~~

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