用堆实现的贪心，分 4 个堆，0 分求调。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>

using namespace std;
typedef long long LL;
const int N=1e6+5;
const LL INF=1e18;
LL cnt,a[N];
priority_queue<LL> Q1,Q2;
priority_queue<LL,vector<LL>,greater<LL> > Q3,Q4;
//Q1正奇 Q2正偶 Q3负奇 Q4负偶 
LL idx,yoimiya;
int n;

void check(int f)
{
	LL x,y;
	if(f)
	{
		if(Q2.size()) x=Q2.top();
		else x=INF;
		if(Q3.size()) y=Q3.top();
		else y=INF;
		if(abs(y)>x)
		{
			Q2.pop();
			a[++cnt]=x+idx;
			idx-=x;
		}
		else
		{
			Q3.pop();
			a[++cnt]=y+idx;
			idx-=abs(y);
		}
	}
	else
	{
		if(Q1.size()) x=Q1.top();
		else x=INF;
		if(Q4.size()) y=Q4.top();
		else y=INF;
		if(abs(y)>x)
		{
			Q1.pop();
			a[++cnt]=x+idx;
			idx-=x;
		}
		else
		{
			Q4.pop();
			a[++cnt]=y+idx;
			idx-=abs(y);
		}
	}
	return;
}

int main()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		LL x;
		scanf("%lld",&x);
		if(x>=0)
		{
			if(x&1) Q1.push(x);
			else Q2.push(x);
		}
		else
		{
			if(x&1) Q3.push(x);
			else Q4.push(x);
		}
	}
	for(i=1;i<=n;i++)
	{
		LL x,y;
		if(i&1)
		{
			if(Q2.size()) x=Q2.top();
			else x=-INF;
			
			if(Q3.size()) y=Q3.top();
			else y=0;
			
			if(Q2.empty()&&Q3.empty()) check(0);
			else if(abs(y)<x)
			{
				Q2.pop();
				a[++cnt]=x+idx;
				idx+=x;
			}
			else
			{
				Q3.pop();
				a[++cnt]=y+idx;
				idx+=abs(y);
			}
		}
		else
		{
			if(Q1.size()) x=Q1.top();
			else x=-INF;
			
			if(Q4.size()) y=Q4.top();
			else y=0;
			
			if(Q1.empty()&&Q4.empty()) check(1);
			else 
			if(abs(y)<x)
			{
				Q1.pop();
				a[++cnt]=x+idx;
				idx+=x;
			}
			else
			{
				Q4.pop();
				a[++cnt]=y+idx;
				idx+=abs(y);
			}
		}
	}
	for(register int e(1);e<=n;++e) yoimiya+=a[e];
	printf("%lld\n",yoimiya);
	return 0;
}