提出 #64589906

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l,i##_e=r;i<=i##_e;++i)
#define rFor(i,r,l) for(int i=r,i##_e=l;i>=i##_e;--i)
#define y0 y_zero
#define y1 y_one
#define all(a) a.begin(),a.end()
#define cmin(a,b) a=min<remove_reference<decltype(a)>::type>(a,b)
#define cmax(a,b) a=max<remove_reference<decltype(a)>::type>(a,b)
#define vect basic_string
// #define ensure(_) ((_) || (__builtin_unreachable(),0))
using namespace std;
using u32=unsigned;
using i64=long long;
using ll=long long;
using u64=unsigned long long;
using ull=unsigned long long;
#if __SIZEOF_POINTER__==8
using i128=__int128;
using u128=__uint128_t;
#endif
using pii=array<int,2>;
using pll=array<ll,2>;
using a3=array<int,3>;
using a4=array<int,4>;
using a5=array<int,5>;
#define mtc() int T; cin>>T; while(T--) work();

const int N=3e5+10;
int n,a[N];
ll sum;
ll f[N],g[N];
void solve() {
	priority_queue<int> q1; priority_queue<int,vector<int>,greater<>> q2;
	ll s1=0,s2=0;
	For(i,1,n-1) {
		int x=a[i],y=a[++i];
		if(x>y) swap(x,y);
		q1.push(x); q2.push(y); s1+=x; s2+=y;
		while(q1.top()>q2.top()) {
			x=q1.top(); q1.pop(); y=q2.top(); q2.pop();
			s1+=y-x; s2+=x-y;
			q1.push(y); q2.push(x);
		}
		f[i]=s2-s1;
	}
}
int main() {
#ifdef LOCAL
	freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	// freopen(".debug","w",stderr);
#endif
#ifndef with_buffer
	ios::sync_with_stdio(0); cin.tie(0);
#endif
	cin>>n;
	For(i,1,n) cin>>a[i];
	if(n%2==0) {
		sort(a+1,a+n+1);
		ll s=0;
		For(i,1,n>>1) s-=a[i],s+=a[n-i+1];
		cout<<s<<"\n";
		return 0;
	}
	solve();
	For(i,1,n) g[i]=f[n-i+1];
	reverse(a+1,a+n+1); solve();
	ll ans=0;
	For(i,1,n) if(i&1) cmax(ans,f[i-1]+g[i+1]);
	cout<<ans<<"\n";
}

提出情報

ジャッジ結果