Submission #3776315

---

Source Code Expand

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { -1, 0, 1, 0 };

int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	int n;
	cin >> n;
	vector<ll> a(3 * n);
	for (int i = 0; i < 3 * n; i++) {
		cin >> a[i];
	}

	vector<ll> front(3 * n + 1); {
		priority_queue<ll, vector<ll>, greater<ll>> que;
		for (int i = 0; i < 3 * n; i++) {
			que.push(a[i]);
			ll b = 0;
			if (que.size() == n + 1) {
				b = que.top(); que.pop();
			}
			front[i + 1] = front[i] + a[i] - b;
		}
	}
	vector<ll> back(3 * n + 1); {
		priority_queue<ll> que;
		for (int i = 3 * n -1; i >= 0; i--) {
			que.push(a[i]);
			ll b = 0;
			if (que.size() == n + 1) {
				b = que.top(); que.pop();
			}
			back[i] = back[i + 1] + a[i] - b;
		}
	}
	ll result = -INT64_MAX;
	for (int i = n; i <= 2 * n; i++) {
		result = max(result, front[i] - back[i]);
	}
	
	cout << result << endl;
	return 0;
}

Submission Info

Judge Result