Submission #1692009

---

Source Code Expand

#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);

  int N, a[333333];

  std::cin >> N;

  for (int i = 0; i < N * 3; i ++)
    std::cin >> a[i];

  std::multiset<int> set;

  long long s = 0, S[333333];

  for (int i = 0; i < N; i ++) {
    set.insert(a[i]);

    s += a[i];
  }

  S[N] = s;

  for (int i = N; i < N * 2; i ++) {
    set.insert(a[i]);

    s += a[i];

    s -= *std::begin(set);

    set.erase(std::begin(set));

    S[i + 1] = s;
  }

  long long dp = -INF;

  s = 0;

  set.clear();

  for (int i = N * 2; i < N * 3; i ++) {
    set.insert(a[i]);

    s += a[i];
  }

  dp = std::max(S[N * 2] - s, dp);
  
  for (int i = N * 2 - 1; i >= N; i --) {
    set.insert(a[i]);

    s += a[i];

    auto it = std::end(set);

    std::advance(it, -1);

    s -= *it;

    set.erase(it);

    dp = std::max(S[i] - s, dp);
  }

  std::cout << dp << std::endl;
  
  return 0;
}

Submission Info

Judge Result