Submission #3018196

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int a[3 * N];
	rep(i, 0, 3 * N) cin >> a[i];

	priority_queue<int> left_q;
	priority_queue<int> right_q;


	ll left_sum[N + 1], right_sum[N + 1];
	memset(left_sum, 0, sizeof(left_sum));
	memset(right_sum, 0, sizeof(right_sum));
	rep(i, 0, N) {
		left_q.push(-a[i]);
		left_sum[0] += a[i];
		right_q.push(a[3 * N - i - 1]);
		right_sum[0] += a[3 * N - i - 1];
	}

	
	rep(i, N, 2 * N) {
		left_q.push(-a[i]);
		ll tmp_l = left_q.top();
		left_q.pop();
		left_sum[i - N + 1] = left_sum[i - N] + tmp_l + a[i];
		right_q.push(a[3 * N - i - 1]);
		ll tmp_r = right_q.top();
		right_q.pop();
		right_sum[i - N + 1] = right_sum[i - N] - tmp_r + a[3 * N - i - 1];
	}

	ll ans = left_sum[0] - right_sum[N];
	rep(i, 0, N + 1) {
		ans = max(ans, left_sum[i] - right_sum[N - i]);
	}
	cout << ans << endl;





}

Submission Info

Judge Result