Submission #64591102

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;

const int mod = 998244353;

int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}

void updAdd(int& a, int b)
{
	a += b;
	if (a >= mod)
		a -= mod;
}

int sub(int a, int b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}

void updSub(int& a, int b)
{
	a -= b;
	if (a < 0)
		a += mod;
}

int mult(int a, int b)
{
	return (LL)a * b % mod;
}

int binpow(int a, LL n)
{
	int res = 1;
	while (n)
	{
		if (n & 1)
			res = mult(res, a);
		a = mult(a, a);
		n /= 2;
	}
	return res;
}

template<typename T>
void updMin(T& a, T b)
{
	a = min(a, b);
}

template<typename T>
void updMax(T& a, T b)
{
	a = max(a, b);
}

struct Multiset
{
	multiset<int> s;
	LL sum;
	void insert(LL x)
	{
		s.insert(x);
		sum += x;
	}
	void erase(LL x)
	{
		auto it = s.find(x);
		assert(it != s.end());
		s.erase(it);
		sum -= x;
	}
};

struct Split
{
	Multiset small, big;
	void insert(LL x)
	{
		if (!big.s.empty() && x >= *big.s.begin())
			big.insert(x);
		else
			small.insert(x);
	}
	void erase(LL x)
	{
		if (small.s.find(x) != small.s.end())
		{
			small.erase(x);
		}
		else
		{
			big.erase(x);
		}
	}
	void rebalance()
	{
		assert((SZ(small.s) + SZ(big.s)) % 2 == 0);
		while (SZ(small.s) > SZ(big.s))
		{
			int x = *prev(small.s.end());
			small.erase(x);
			big.insert(x);
		}
		while (SZ(big.s) > SZ(small.s))
		{
			int x = *big.s.begin();
			big.erase(x);
			small.insert(x);
		}
	}
};

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	int n;
	cin >> n;
	VI a(n);
	for (int& ai : a)
		cin >> ai;
	if (n % 2 == 1)
	{
		Split sLeft, sRight;
		FOR(i, 1, n)
		{
			sRight.insert(a[i]);
		}
		sRight.rebalance();
		LL ans = sRight.big.sum - sRight.small.sum;
		for (int i = 2; i < n; i += 2)
		{
			sLeft.insert(a[i - 2]);
			sLeft.insert(a[i - 1]);
			sLeft.rebalance();
			sRight.erase(a[i - 1]);
			sRight.erase(a[i]);
			sRight.rebalance();
			updMax(ans, sLeft.big.sum - sLeft.small.sum + sRight.big.sum - sRight.small.sum);
		}
		cout << ans << "\n";
		return 0;
	}
	Split s;
	FOR(i, 0, n)
	{
		s.insert(a[i]);
	}
	s.rebalance();
	cout << s.big.sum - s.small.sum << "\n";
	return 0;
}

Submission Info

Judge Result