# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1129386 | NAMIN | Detecting Molecules (IOI16_molecules) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
vector<bool> take;
pair<vector<int>,bool> solve(int l,int u,vector<pair<int,int>>& W){
if(l <= 0)
return {{},true};
vector<int> ans;
bool ok = false;
for(int i=0;i<W.size();i++){
if(W[i].first > u || take[i])
continue;
take[i] = true;
auto res = find_subset(l-W[i].first,u-W[i].first);
ans = res.first;
ans.push_back(W[i].second);
ok = res.second;
if(ok){
break;
}
take[i] = false;
}
return {ans,ok};
}
vector<int> find_subset(int l, int u,vector<int> w) {
take.assign(w.size(),false);
vector<pair<int,int>> W;
for(int i=0;i<w.size();i++){
W.push_back(make_pair(w[i],i));
}
sort(W.begin(),W.end());
return solve(l,u,W).first;
}