Submission #230982

#	Time	Username	Problem	Language	Result	Execution time	Memory
230982		peijar	Detecting Molecules (IOI16_molecules)	C++17	46 / 100	362 ms	65540 KiB

molecules

#include <bits/stdc++.h>
using namespace std;

#define SZ(v) ((int)(v).size())

vector<int> find_subset(int l, int r, vector<int> weights)
{
	int nb_poids = SZ(weights);
	vector<int> ans;

	vector<vector<bool> > can_reach(nb_poids, vector<bool>(r+1, false));

	for (int id_poids(0); id_poids < nb_poids; ++id_poids)
		for (int want(0); want <= r; ++want)
			can_reach[id_poids][want] = (id_poids ? can_reach[id_poids-1][want] : false)
			 or (id_poids and want >= weights[id_poids] ? can_reach[id_poids-1][want-weights[id_poids]] : !want or want==weights[id_poids]);

	for (int cur_weight(l); cur_weight <= r; ++cur_weight)
		if (can_reach[nb_poids-1][cur_weight])
		{
			int cur_id = nb_poids - 1;
			while (cur_weight> 0)
			{
				if (!cur_id or !can_reach[cur_id-1][cur_weight])
				{
					ans.push_back(cur_id);
					cur_weight -= weights[cur_id];
				}
				--cur_id;
			}
			return ans;
		}
	return ans;
}

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