Submission #1746297

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <functional>

#define N 100000

using namespace std;

int parent(int i){return((i-1)/2);}
int lchild(int i){return(2*i+1);}
int rchild(int i){return(2*i+2);}

bool gt(int x, int y){
  return(x > y);
}

bool lt(int x, int y){
  return(x < y);
}

void push(int x, int *pq, int *q_max, function<bool(int, int)> f){
  pq[*q_max] = x;
  int idx = *q_max;
  (*q_max)++;
  while (idx > 0) {
    if (f(pq[idx], pq[parent(idx)])) {
      int tmp = pq[parent(idx)];
      pq[parent(idx)] = pq[idx];
      pq[idx] = tmp;
      idx = parent(idx);
    } else {
      return;
    }
  }
}

int pop(int *pq, int *q_max, function<bool(int, int)> f){
  if (*q_max < 0) {
    cerr << "queue is empty." << endl;
    return 0;
  }
  int result = pq[0];
  pq[0] = pq[--(*q_max)];
  int idx = 0;
  while (lchild(idx) < *q_max) {
    if (f(pq[idx], pq[lchild(idx)]) && f(pq[idx], pq[rchild(idx)])) {
      return(result);
    }
    if (f(pq[lchild(idx)], pq[rchild(idx)])) {
      int tmp = pq[lchild(idx)];
      pq[lchild(idx)] = pq[idx];
      pq[idx] = tmp;
      idx = lchild(idx);
    } else {
      int tmp = pq[rchild(idx)];
      pq[rchild(idx)] = pq[idx];
      pq[idx] = tmp;
      idx = rchild(idx);
    } 
  }
  return(result);
}


int main(){
  int n;
  int a1_pq[N+1], a2[N+1], a3_pq[N+1];
  int a1_pq_max = 0;
  int a3_pq_max = 0;
  long long a1_max[N+1], a3_min[N+1];
  cin >> n;
  a1_max[0] = 0;
  a3_min[n] = 0;
  for (int i=0;i<n;i++) {
    int a;
    cin >> a;
    push(a, a1_pq, &a1_pq_max, lt);
    a1_max[0] += a;
  }
  for (int i=0;i<n;i++) {
    int a;
    cin >> a;
    a2[i] = a;
  }
  for (int i=0;i<n;i++) {
    int a;
    cin >> a;
    push(a, a3_pq, &a3_pq_max, gt);
    a3_min[n] += a;
  }
  for (int i=0;i<n;i++) {
    if (a1_pq[0] < a2[i]) {
      a1_max[i+1] = a2[i] - a1_pq[0] + a1_max[i];
      pop(a1_pq, &a1_pq_max, lt);
      push(a2[i], a1_pq, &a1_pq_max, lt);
    } else {
      a1_max[i+1] = a1_max[i];
    }
  }
  for (int i=n;i>0;i--) {
    if (a3_pq[0] > a2[i-1]) {
      a3_min[i-1] = a2[i-1] - a3_pq[0] + a3_min[i];
      pop(a3_pq, &a3_pq_max, gt);
      push(a2[i-1], a3_pq, &a3_pq_max, gt);
    } else {
      a3_min[i-1] = a3_min[i];
    }
  }
  long long result = LLONG_MIN;
  for (int i=0;i<=n;i++) {
    if (a1_max[i] - a3_min[i] > result) {
      result = a1_max[i] - a3_min[i];
    }
  }
  cout << result << endl;  
}

Submission Info

Judge Result