# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88629 | 2018-12-07T07:59:15 Z | Nucleist | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KB |
#include "molecules.h" #include <bits/stdc++.h> using namespace std; vector<int> find_subset(int l, int u, std::vector<int> w) { int k = w.size(); int f = l; int compteur=0; l=u; int n = k; vector <int> kk; int sum = max(f,l); bool subset[k+1][max(f,l)+1]; for (int i = 0; i <= n; i++) subset[i][0] = true; for (int i = 1; i <= sum; i++) subset[0][i] = false; for (int i = 1; i <= n; i++) { for (int j = 1; j <= sum; j++) { if(j<w[i-1]) subset[i][j] = subset[i-1][j]; if (j >= w[i-1]) subset[i][j] = subset[i-1][j] || subset[i - 1][j-w[i-1]]; } } bool ka = false; for (int j = min(l,f); j <= max(l,f); j++) { int kaa=j; if(subset[n][j]) { for(int i = n;i>=1;i--) { if(subset[i-1][kaa-w[i-1]]) { kk.push_back(w[i-1]); kaa -= w[i-1]; compteur++; ka=true; if(kaa==0) break; } } } if(ka) break; } return std::vector<int>kk; }