Submission #117112

#	Time	Username	Problem	Language	Result	Execution time	Memory
117112		Lawliet	Detecting Molecules (IOI16_molecules)	C++17	46 / 100	111 ms	768 KiB

molecules

#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;
		}
	}
}

std::vector<int> find_subset(int l, int u, std::vector<int> w)
{
	L = l; U = u;

	N = w.size();

	//for(int g = 0 ; g < N ; g++)
		//printf("%d\n",w[g]);

	ans.clear();
	memset(dp , false , sizeof(dp));
	memset(indAnt , -1 , sizeof(indAnt));
	memset(valueAnt , -1 , sizeof(valueAnt));

	dp[0] = true;

	for(int g = 0 ; g < N ; g++)
		add( w[g] , g );

	int can = -1;

	//for(int g = 1 ; g <= U ; g++)
		//printf("-> %d %d\n",g,dp[g]);

	for(int g = L ; g <= U ; g++)
		if(dp[g]) can = g;

	//printf("can = %d\n",can);

	if(can == -1) return ans;

	while( indAnt[can] != -1 )
	{
		ans.push_back( indAnt[can] );

		can -= valueAnt[can];
	}

	//printf("-> %d\n",ans.size());

	return ans;
}

/*int main()
{
	scanf("%d %d %d",&N,&L,&U);

	vector<int> W(N);

	for(int g = 0 ; g < N ; g++)
		scanf("%d",&W[g]);

	printf("%d\n",find_subset(L , U , W).size());
}*/

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