This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |