提出 #1296984

---

ソースコード 拡げる

/*{{{*/
// think twice code once
// Start:[]
// End  :[]
#include <bits/stdc++.h>
using namespace std;

#define rep(i, x, y) for(int i = (x), _ = (y); i <= _; ++ i)
#define per(i, x, y) for(int i = (x), _ = (y); i >= _; -- i)
#define dprintf(...) fprintf(stderr, __VA_ARGS__)
#define disp(x) cout << #x << " = " << x << "; "
#define x first
#define y second
#define mp make_pair
#ifdef __linux__
#define getchar getchar_unlocked
#define LLFORMAT "%lld"
#else
#define LLFORMAT "%I64d"
#endif

typedef long long LL;

template <class T> bool chkmin(T& a, T b) { return a > b ? a = b, true : false; }
template <class T> bool chkmax(T& a, T b) { return a < b ? a = b, true : false; }

template <class T> void read(T& a) {
	char c = getchar(); T f = 1; a = 0;
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) a = a * 10 + c - '0';
	a *= f;
}
/*}}}*/

const int maxN = 3e5 + 5;

priority_queue<int, vector<int>, greater<int> > q;
LL pre[maxN], suf[maxN];
LL sum;
int N, a[maxN], b[maxN];

int main()
{
#ifdef Leeson
	freopen("tmp.in", "r", stdin);
	freopen("tmp.out", "w", stdout);
#endif

	LL ans = LLONG_MIN;
	read(N);
	rep(i, 1, N * 3) read(a[i]), b[i] = -a[i];
	rep(i, 1, N * 3)
	{
		q.push(a[i]);
		sum += a[i];
		if((int)q.size() > N) 
			sum -= q.top(), q.pop();
		pre[i] = sum;
	}
	while(!q.empty()) q.pop();
	sum = 0;
	per(i, N*3, 1)
	{
		sum += b[i];
		q.push(b[i]);
		if((int)q.size() > N)
			sum -= q.top(), q.pop();
		suf[i] = sum;
	}
	rep(i, N, 2*N)
		chkmax(ans, pre[i] + suf[i + 1]);
	//rep(i, 1, N*3)
	//{
	//	printf("%lld\n", pre[i]);
	//}
	//per(i, N*3, 1)
	//{
	//	printf("%lld\n", suf[i]);
	//}

	cout << ans << endl;
	return 0;
}

提出情報

ジャッジ結果