（其实这一题是我从一道树形dp里面扒来的，原题大概是定义dp状态为以i为根，遍历这个子树的状态是奇数/偶数 时可以获得的最大值。然后状态转移的时候就要用到本题类似的解法来取最优状态。我当时写完感觉这个部分也很有意思，所以把这个部分抽出来出了一题，但是也不算完全一样）

我们考虑一下，发现我们并不关心时间具体是多少，因为所有比赛的得分都只基于当前时间的奇偶性，所以接下来我们只需要讨论时间的奇偶性。

考虑一场偶数时间用时的比赛，可以发现打这场比赛对当前时间的奇偶性没有影响，而打奇数时间的比赛会让当前时间从偶数变成奇数，从奇数变成偶数。

你注意到了吗？也就是说只要存在奇数用时的比赛，我们就可以任意选择偶数用时比赛的开始时间奇偶性。

假设我们有 $x$ 场奇数用时比赛，那么就会有 $x/2$ 场奇数用时比赛时间比赛需要以奇数时间开始，剩下的比赛就要选择偶数时间开始。而偶数用时的比赛则可以任意安排，取奇偶时间得分的最大值即可。

特别地，我们还要选择开始时间的奇偶性。开始时间的奇偶性分别对应了 $x/2$ 是上取整还是下取整，可以自己推一下。另外如果全都是偶数用时比赛的话，那么我们无法改变时间奇偶性，所以答案只能是所有比赛偶数时间得分，和所有比赛奇数时间得分取最大值。

那么我们如何选择最优的 $x/2$ 个奇数时间比赛呢？显然可以 反悔贪心。详见代码

#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int n,jnum;
int m[100001],x[100001],y[100001];
bool all_o=true;

int main()
{
	//freopen("cmpe019.in","r",stdin);
	//freopen("cmpe019.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>m[i]>>x[i]>>y[i];
		if(m[i]%2!=0) all_o=false,jnum++;//奇数会改变时间奇偶性 
	}
	long long xpre=0,ypre=0;
	for(int i=1;i<=n;i++)
	{
		xpre+=x[i];
		ypre+=y[i];
	}
	if(all_o)
	{	cout<<max(xpre,ypre);//都是偶数，则不会改变奇偶性，选择最大的即可 
		return 0;
	}
	long long ans=0;
	priority_queue<int> q;
	for(int i=1;i<=n;i++)
	{
		if(m[i]%2==0)//是偶数，不会改变奇偶性，于是可以插入任意奇偶段来比赛 
		{
			ans+=max(x[i],y[i]);
			//cout<<ans<<endl; 
		}
		else
		{
			ans+=x[i]; 
			q.push(y[i]-x[i]);//反悔贪心 
		}
	}
	for(int i=1;i<=jnum/2;i++)//最多jnum/2次改变奇偶性的机会 
	{
		ans+=q.top();
		//cout<<ans<<endl;
		q.pop();
	}
	if(jnum%2!=0) ans=max(ans,ans+q.top()); 
	cout<<ans;
	return 0;
}