Submission #491999

#	Time	Username	Problem	Language	Result	Execution time	Memory
491999		eNGy	Detecting Molecules (IOI16_molecules)	C++17	0 / 100	1083 ms	204 KiB

molecules

#include <bits/stdc++.h>
#define c(x) (cerr << __LINE__ << ": " << #x << ' ' << (x) << endl, (x))
#define vis() (cerr << __LINE__ << endl)

using namespace std;

int N;
vector<int> sol;

bool dfs(int n, int s, int l, int u, vector<int> &w, bool v[]){
	v[n] = 1;
	sol.push_back(n);
	if(s > u){
		sol.pop_back();
		return false;
	}else if(s >= l){
		return true;
	}
	
	for(int i=0; i<N; i++){
		if(!v[i]){
			if(dfs(i, s + w[i], l, u, w, v)){
				
				return true;
			}
		}
	}
	v[n] = 0;
	sol.pop_back();
	return false;
}

vector<int> find_subset(int l, int u, vector<int> w){
	N = w.size();
	int i = 0;
	
	bool v[N];
	fill(v, v+N, 0);
	
	while(i < N && !dfs(i, w[i], l, u, w, v)){
		i++;
	}
	
	return sol;
}

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