優先度付きキュー(ABC 062 D問題)

便利だね
問題
以下ネタバレ注意

1. ll a[300030];
2. ll Left[3000030], Right[300030];
3. int main() {
4. int N;
5. cin >> N;
6. REP(i, 3 * N) {
7. cin >> a[i];
8. }
9.  
10.  
11. ll left = 0;
12. //小さい順に取り出す
13. priority_queue<ll, vector<ll>, greater<ll>> minpq;
14. REP(i, N) {
15. left += a[i];
16. minpq.push(a[i]);
17. }
18. Left[N-1] = left;
19. FOR(i, N, 2*N) {
20. minpq.push(a[i]);
21. Left[i] =Left[i-1]+ a[i];
22. ll c = minpq.top();
23. minpq.pop();
24. Left[i]-= c;
25. }
26.  
27.  
28. ll right = 0;
29. priority_queue<ll> maxpq;
30. FORR(i, 3*N - 1, 2*N) {
31. right += a[i];
32. maxpq.push(a[i]);
33. }
34. Right[2 * N] = right;
35. FORR(i, 2*N - 1, N-1) {
36. Right[i] =Right[i+1]+ a[i];
37. maxpq.push(a[i]);
38. ll c = maxpq.top();
39. maxpq.pop();
40. Right[i] -= c;
41. }
42.  
43. ll ans = -9999999999999999;
44. FOR(i,N, 2 * N+1) {
45. ans = max(ans, (Left[i - 1] - Right[i]));
46. }
47. cout << ans << endl;
48. }