Submission #200876

#	Time	Username	Problem	Language	Result	Execution time	Memory
200876		oofsauce	Detecting Molecules (IOI16_molecules)	C++14	46 / 100	259 ms	65540 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(w > u) return false;
  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(weights.size()+5, vector<bool>(l+5,false));

  recurse(0,0);

  return ans;
}

Compilation message (stderr)

molecules.cpp: In function 'bool recurse(int, int)':
molecules.cpp:16: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: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31