Submission #115047

#	Time	Username	Problem	Language	Result	Execution time	Memory
115047		luciocf	Tug of War (BOI15_tug)	C++14	41 / 100	117 ms	920 KiB

tug

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int l[maxn], r[maxn], s[maxn], grau[maxn];

bool mark[maxn];

int main(void)
{
	int n, k;
	scanf("%d %d", &n, &k);

	for (int i = 1; i <= 2*n; i++)
	{
		scanf("%d %d %d", &l[i], &r[i], &s[i]);
		r[i] += n;

		grau[l[i]]++, grau[r[i]]++;
	}

	if (n > 10)
	{
		bool ok = 1;
		for (int i = 1; i <= 2*n; i++)
			if (!grau[i])
				ok = 0;

		if (ok) printf("YES\n");
		else printf("NO\n");

		return 0;
	}

	bool ans = 0;

	for (int mask = 0; mask < (1<<(2*n)); mask++)
	{
		bool ok = 1;

		for (int i = 1; i <= 2*n; i++)
			mark[i] = 0;

		for (int i = 0; i < 2*n; i++)
		{
			if (mask&(1<<i))
			{
				if (mark[r[i+1]]) ok = 0;
				else mark[r[i+1]] = 1;
			}
			else
			{
				if (mark[l[i+1]]) ok = 0;
				else mark[l[i+1]] = 1;
			}
		}

		if (!ok) continue;

		int sa = 0, sb = 0;

		for (int i = 0; i < 2*n; i++)
		{
			if (mask&(1<<i))
				sb += s[i+1];
			else
				sa += s[i+1];
		}

		if (abs(sa-sb) <= k)
		{
			ans = 1;
			break;
		}
	}

	if (ans == 1) printf("YES\n");
	else printf("NO\n");
}

Compilation message (stderr)

tug.cpp: In function 'int main()':
tug.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
tug.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &l[i], &r[i], &s[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 0 / 30
• Subtask 3: 23 / 23
• Subtask 4: 0 / 29