UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4124. [Baltic2015]Tug of war

Statistics 下载数据

Description

2n个人分成n+n两个团队拔河,每个人有一个实力Si,每个人在左侧和右侧都有一个理想位
置分别为Li和Ri。问是否可以将这2n个人分成两个团队,保证每个人都在一个自己的理想位
置上并且两方实力差距不超过k

Input

第一行输入n,k。
接下来2n行,每行输入三个正整数Li,Ri和Si

Output

输出YES或者NO

Sample Input

4 1
1 1 1
2 1 2
2 2 8
1 2 2
3 3 5
3 3 2
4 4 1
4 4 2

Sample Output

YES
样例解释:在第一个样例中,我们可以将参赛者1,3,6和7分配到左侧(产生一支力量为1+8+
2+1=12的团队),将参赛者2,4,5和8 到右侧(产生一支力量为2+2+5+2=11的团队),团队
之间的优势差距是1

Hint

Source

鸣谢zP1nG提供译文