Submission #949221

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
949221	2024-03-19T03:56:56 Z	Faisal_Saqib	Tug of War (BOI15_tug)	C++17	18 / 100	1 ms	604 KB

tug

#include <bits/stdc++.h>
using namespace std;
const int N=21;
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.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	452 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	1 ms	448 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	456 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	0 ms	456 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct

Subtask #2

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	452 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	1 ms	448 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	456 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	0 ms	456 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Runtime error	1 ms	604 KB	Execution killed with signal 11
27	Halted	0 ms	0 KB	-

Subtask #3

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	604 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	452 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	1 ms	448 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	456 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	0 ms	456 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Runtime error	1 ms	604 KB	Execution killed with signal 11
27	Halted	0 ms	0 KB	-