Submission #64589663

---

Source Code Expand

// created:  2025-04-06 20:01:26
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#define F(i,l,r) for(int i=(l),i##_end=(r);i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>constexpr bool is_integral_128=(bool)is_integral<T>::value I128;
template<typename T>struct read_dec1{enable_if_t<is_integral_128<T>,T> &x;};
constexpr struct read_dec1_conv{template<typename T>read_dec1<T> operator+(T &x)const{return read_dec1<T>{x};}}D;
template<typename T>enable_if_t<is_integral_128<T>,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>void readmain(read_dec1<T> &y){readmain(y.x);--y.x;}
template<typename T>T& read(T &&x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &&x,Tr&&... r){readmain(x);read(r...);}
typedef long long ll;
constexpr int N=3e5+5;
struct ds
{
	priority_queue<int> p1;
	priority_queue<int,vector<int>,greater<int>> p2;
	ll s;
	void clear()
	{
		while(!p1.empty())p1.pop();
		while(!p2.empty())p2.pop();
		s=0;
	}
	void push(int x,int y)
	{
		if(x>y)swap(x,y);
		p1.emplace(x);p2.emplace(y);
		s+=y-x;
		while(p1.top()>p2.top())
		{
			x=p1.top();p1.pop();
			y=p2.top();p2.pop();
			p1.emplace(y);p2.emplace(x);
			s+=2*(x-y);
		}
	}
}s;
int n,a[N];
ll pre[N],suf[N];
int main()
{
	read(n);
	F(i,0,n)read(a[i]);
	for(int i=0;i+1<n;i+=2)
	{
		s.push(a[i],a[i+1]);
		pre[i+2]=s.s;
	}
	s.clear();
	for(int i=n-2;i>=0;i-=2)
	{
		s.push(a[i],a[i+1]);
		suf[i]=s.s;
	}
	ll ans=0;
	if(n&1)for(int i=0;i<n;i+=2)ans=max(ans,pre[i]+suf[i+1]);
	else ans=pre[n];
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Judge Result