8275

static int N, X, M, L, R, S, turn, maximum = -1;
static int equation[6 + 1];
static int grps[6 + 1];
static int ans[6 + 1];
static vector<target> all[10];

static void get_all_comb(int cnt, int v)
{
	if (cnt > N)
	{
		if (v == S)
		{
			target c(7);
			for (int i = 1; i < cnt; i++)
				c[i] = grps[i];
			all[turn].push_back(c);
		}
		return;
	}

	if (equation[cnt])
	{
		for (int i = 0; i <= X; i++)
		{
			int val = v + i;
			grps[cnt] = i;
			get_all_comb(cnt + 1, val);
		}
	}
	else
	{
		grps[cnt] = -1;
		get_all_comb(cnt + 1, v);
	}
}

static void check(int cnt)
{
	if (cnt == turn)
	{
		int value = 0;
		for (int j = 1; j <= N; j++)
		{
			if (grps[j] < 0)
				value += X;
			else
				value += grps[j];
		}

		if (value > maximum)
		{
			memcpy(ans, grps, sizeof(grps));
			maximum = value;
		}
		else if (value == maximum)
		{
			//ans보다 앞서는 경우에만 초기화.
		}
		return;
	}

	vector<target> &v = all[cnt];
	int * cpy = new int[7];

	memcpy(cpy, grps, sizeof(grps));
	for (int i = 0; i < v.size(); i++)
	{
		int j;
		for (j = 1; j <= N; j++)
		{
			if (grps[j] < 0)
				grps[j] = v[i][j];
			else if (v[i][j] >= 0 && grps[j] != v[i][j])
				break;
		}
		if (j > N)
			check(cnt + 1);
		memcpy(grps, cpy, sizeof(grps));
	}
	delete[]cpy;
}

static void solution(void)
{
	scanf("%d %d %d", &N, &X, &M);
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d %d", &L, &R, &S);
		for (int j = L; j <= R; j++)
			equation[j] = 1;

		get_all_comb(1, 0);
		turn += 1;
		memset(equation, 0, sizeof(equation));
	}

	memset(grps, -1, sizeof(grps));
	check(0);
	if (maximum < 0)
		printf("-1\n");
	else
	{
		for (int i = 1; i <= N; i++)
		{
			if (ans[i] < 0)
				printf("%d ", X);
			else
				printf("%d ", ans[i]);
		}
		puts("");
	}

	for (int i = 0; i < turn; i++)
		all[i].clear();
	turn = 0;
	maximum = -1;
}

입력으로 받은 중복 조합을 모두 구한 뒤, 모든 경우를 점검하도록 한다.