418B


  Posted on 13 Dec 2014
dynamic programming bitmasks

Solution


#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 110;
const int MAX_M = 20;
const long long INF = (1LL << 60);

struct Elem
{
	Elem()
	{}

	Elem(int ruble, int monitor, int prob):ruble(ruble), monitor(monitor), prob(prob)
	{}

	int ruble, monitor, prob;

	bool operator < (const Elem &b) const
	{
		return monitor < b.monitor;
	}
}elem[MAX_N];

int n, m, price;
long long f[1 << MAX_M];

int main()
{
	//input
	scanf("%d%d%d", &n, &m, &price);
	for (int i = 0; i < n; i++)
	{
		int a, b, c, d, e = 0;
		scanf("%d%d%d", &a, &b, &c);
		for (int j = 0; j < c; j++)
		{
			scanf("%d", &d);
			d--;
			e = e | (1 << d);
		}
		elem[i] = Elem(a, b, e);
	}

	//work
	long long ans = INF;
	sort(elem, elem + n);
	fill(f, f + (1 << m), INF);
	f[0] = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < (1 << m); j++)
		{
			f[j | elem[i].prob] = min(f[j | elem[i].prob], f[j] + elem[i].ruble);
		}
		ans = min(ans, f[(1 << m) - 1] + 1LL * price * elem[i].monitor);
	}
	if (ans == INF)
		puts("-1");
	else
		printf("%I64d\n", ans);
	return 0;
}