제출 #949223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
949223		Faisal_Saqib	Tug of War (BOI15_tug)	C++17	18 / 100	3051 ms	860 KiB

tug

#include <bits/stdc++.h>
using namespace std;
const int N=4001;
int l[N],r[N],s[N],k;
int midif=1e9;
void choose(int total,int cho,set<int>& left,set<int>& right,int suml=0,int sumr=0)
{
	if(cho==0 and total==0)
	{

		midif=min(midif,abs(suml-sumr));
		if(midif<=k)
		{
			cout<<"YES\n";
			exit(0);
		}
		return;
	}
	if(total==0)
		return;
	{
		// Case#1: We don't take total
		auto it=left.find(l[total]);
		if(it!=left.end())
		{
			left.erase(it);
			choose(total-1,cho,left,right,suml+s[total],sumr);			
			left.insert(l[total]);
		}
	}
	if(cho!=0)
	{
		// Case#2: We Go to right side
		auto it=right.find(r[total]);
		if(it!=right.end())
		{
			right.erase(it);
			choose(total-1,cho-1,left,right,suml,sumr+s[total]);			
			right.insert(r[total]);
		}
	}
}
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	int n;
	cin>>n>>k;
	for(int i=1;i<=(2*n);i++)
		cin>>l[i]>>r[i]>>s[i];
	set<int> left,right;
	for(int i=1;i<=n;i++)
	{
		left.insert(i);
		right.insert(i);
	}
	choose(2*n,n,left,right);
	cout<<"NO\n";
	return 0;
}

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