# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
117108 | 2019-06-14T21:17:32 Z | Lawliet | Detecting Molecules (IOI16_molecules) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "molecules.h" #define MAX 10010 using namespace std; int N, L, U; int indAnt[MAX]; int valueAnt[MAX]; bool dp[MAX]; vector<int> ans; void add(int w, int i) { for(int g = U ; g >= w ; g--) { if(dp[g - w] && !dp[g]) { dp[g] = true; indAnt[g] = i; valueAnt[g] = w; } } } int[] find_subset(int l, int u, int[] w) { L = l; U = u; dp[0] = true; ans.clear(); memset(dp , false , sizeof(dp)); memset(indAnt , -1 , sizeof(indAnt)); memset(valueAnt , -1 , sizeof(valueAnt)); int ind = 0; while( w[ind] != 0 ) { add( w[ind] , ind); ind++; } int can = -1; for(int g = L ; g <= U ; g++) if(dp[g]) can = g; if(can == -1) { int resp[0]; //return resp; //printf("N\n"); return resp; } while( indAnt[can] != -1 ) { ans.push_back( indAnt[can] ); can -= valueAnt[can]; } int resp[ans.size()]; for(int g = 0 ; g < ans.size() ; g++) resp[g] = ans[g]; return resp; } /*int main() { scanf("%d %d %d",&N,&L,&U); int W[N]; for(int g = 0 ; g < N ; g++) scanf("%d",&W[g]); find_subset(L , U , W); }*/