Problem:


Score : 500 points

Problem Statement

Let N be a positive integer.

There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}).
Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements.
Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').

Find the maximum possible score of a'.

Constraints

1 ≤ N ≤ 10^5

a_i is an integer.

1 ≤ a_i ≤ 10^9

Partial Score

In the test set worth 300 points, N ≤ 1000.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{3N}

Output

Print the maximum possible score of a'.

Sample Input 1

2
3 1 4 1 5 9

Sample Output 1

1

When a_2 and a_6 are removed, a' will be (3, 4, 1, 5), which has a score of (3 + 4) - (1 + 5) = 1.

Sample Input 2

1
1 2 3

Sample Output 2

-1

For example, when a_1 are removed, a' will be (2, 3), which has a score of 2 - 3 = -1.

Sample Input 3

3
8 2 2 7 4 6 5 3 8

Sample Output 3

5

For example, when a_2, a_3 and a_9 are removed, a' will be (8, 7, 4, 6, 5, 3), which has a score of (8 + 7 + 4) - (6 + 5 + 3) = 5.



Sample input:
2
3 1 4 1 5 9


Sample output:
1

Submission status: Accepted

Solution code:
code_cppset = r"""
#include <Python.h>
#include <vector>
#undef __GNUC__  // g++ 拡張を使わない場合はここのコメントアウトを外すと高速になる
#ifdef __GNUC__
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    using namespace std;
    using namespace __gnu_pbds;
    const static auto comp_pyobj = [](PyObject* const & lhs, PyObject* const & rhs){
        return (bool)PyObject_RichCompareBool(lhs, rhs, Py_LE);  // 比較できない場合 -1
    };
    using pb_set = tree<
        PyObject*,
        null_type,
        decltype(comp_pyobj),
        rb_tree_tag,
        tree_order_statistics_node_update
    >;
#else
    #include <set>
    using namespace std;
    const static auto comp_pyobj = [](PyObject* const & lhs, PyObject* const & rhs){
        return (bool)PyObject_RichCompareBool(lhs, rhs, Py_LE);
    };
    using pb_set = set<PyObject*, decltype(comp_pyobj)>;
#endif
#define PARSE_ARGS(types, ...) if(!PyArg_ParseTuple(args, types, __VA_ARGS__)) return NULL
#define GET_POINTER(stCapsule) (Set4PyObject*)PyCapsule_GetPointer(stCapsule, "Set4PyObjectPtr")

struct Set4PyObject{
    pb_set st;
    pb_set::iterator it;
    Set4PyObject() : st(comp_pyobj), it(st.begin()) {}
    Set4PyObject(vector<PyObject*>& vec) : st(vec.begin(), vec.end(), comp_pyobj), it(st.begin()) {}
    Set4PyObject(const Set4PyObject& obj) : st(obj.st), it(st.begin()) {
        for(PyObject* const & p : st) Py_INCREF(p);
    }
    ~Set4PyObject(){
        for(PyObject* const & p : st) Py_DECREF(p);
    }
    bool add(PyObject* x){
        const auto& r = st.insert(x);
        it = r.first;
        if(r.second){
            Py_INCREF(x);
            return true;
        }else{
            return false;
        }
    }
    PyObject* remove(PyObject* x){
        it = st.find(x);
        if(it == st.end()) return PyErr_SetObject(PyExc_KeyError, x), (PyObject*)NULL;
        Py_DECREF(*it);
        it = st.erase(it);
        if(it == st.end()) return Py_None;
        return *it;
    }
    PyObject* search_higher_equal(PyObject* x){
        it = st.lower_bound(x);
        if(it == st.end()) return Py_None;
        return *it;
    }
    PyObject* min(){
        if(st.size()==0)
            return PyErr_SetString(PyExc_IndexError, "min from an empty set"), (PyObject*)NULL;
        it = st.begin();
        return *it;
    }
    PyObject* max(){
        if(st.size()==0)
            return PyErr_SetString(PyExc_IndexError, "min from an empty set"), (PyObject*)NULL;
        it = prev(st.end());
        return *it;
    }
    PyObject* pop_min(){
        if(st.size()==0)
            return PyErr_SetString(PyExc_IndexError, "pop_min from an empty set"), (PyObject*)NULL;
        it = st.begin();
        PyObject* res = *it;
        it = st.erase(it);
        return res;
    }
    PyObject* pop_max(){
        if(st.size()==0)
            return PyErr_SetString(PyExc_IndexError, "pop_max from an empty set"), (PyObject*)NULL;
        it = prev(st.end());
        PyObject* res = *it;
        it = st.erase(it);
        return res;
    }
    size_t len() const {
        return st.size();
    }
    PyObject* iter_next(){
        if(it == st.end()) return Py_None;
        if(++it == st.end()) return Py_None;
        return *it;
    }
    PyObject* iter_prev(){
        if(it == st.begin()) return Py_None;
        return *--it;
    }
    PyObject* to_list() const {
        PyObject* list = PyList_New(st.size());
        int i = 0;
        for(PyObject* const & p : st){
            Py_INCREF(p);
            PyList_SET_ITEM(list, i++, p);
        }
        return list;
    }
    PyObject* get() const {
        if(it == st.end()) return Py_None;
        return *it;
    }
    PyObject* erase(){
        if(it == st.end()) PyErr_SetString(PyExc_KeyError, "erase end"), (PyObject*)NULL;
        PyObject* res = *it;
        it = st.erase(it);
        if(it == st.end()) return Py_None;
        return *it;
    }
    PyObject* getitem(const long& idx){
        long idx_pos = idx >= 0 ? idx : idx + (long)st.size();
        if(idx_pos >= st.size() || idx_pos < 0)
            return PyErr_Format(
                PyExc_IndexError,
                "cppset getitem index out of range (size=%d, idx=%d)", st.size(), idx
            ), (PyObject*)NULL;
        #ifdef __GNUC__
            it = st.find_by_order(idx_pos);
        #else
            it = st.begin();
            for(int i=0; i<idx_pos; i++) it++;
        #endif
        return *it;
    }
    PyObject* pop(const long& idx){
        long idx_pos = idx >= 0 ? idx : idx + (long)st.size();
        if(idx_pos >= st.size() || idx_pos < 0)
            return PyErr_Format(
                PyExc_IndexError,
                "cppset pop index out of range (size=%d, idx=%d)", st.size(), idx
            ), (PyObject*)NULL;
        #ifdef __GNUC__
            it = st.find_by_order(idx_pos);
        #else
            it = st.begin();
            for(int i=0; i<idx_pos; i++) it++;
        #endif
        PyObject* res = *it;
        it = st.erase(it);
        return res;
    }
    long index(PyObject* x) const {
        #ifdef __GNUC__
            return st.order_of_key(x);
        #else
            long res = 0;
            pb_set::iterator it2 = st.begin();
            while(it2 != st.end() && comp_pyobj(*it2, x)) it2++, res++;
            return res;
        #endif
    }
};

void Set4PyObject_free(PyObject *obj){
    Set4PyObject* const p = (Set4PyObject*)PyCapsule_GetPointer(obj, "Set4PyObjectPtr");
    delete p;
}
PyObject* Set4PyObject_construct(PyObject* self, PyObject* args){
    Set4PyObject* st = new Set4PyObject();
    return PyCapsule_New((void*)st, "Set4PyObjectPtr", Set4PyObject_free);
}
PyObject* Set4PyObject_construct_from_list(PyObject* self, PyObject* args){
    PyObject* lst;
    PARSE_ARGS("O", &lst);
    int siz;
    if(PyList_Check(lst)) siz = (int)PyList_GET_SIZE(lst);
    else if(PyTuple_Check(lst)) siz = (int)PyTuple_GET_SIZE(lst);
    else PyErr_SetString(PyExc_TypeError, "got neither list nor tuple");
    vector<PyObject*> vec(siz);
    for(int i=0; i<siz; i++){
        vec[i] = PyList_Check(lst) ? PyList_GET_ITEM(lst, i) : PyTuple_GET_ITEM(lst, i);
        Py_INCREF(vec[i]);
    }
    Set4PyObject* st = new Set4PyObject(vec);
    return PyCapsule_New((void*)st, "Set4PyObjectPtr", Set4PyObject_free);
}
PyObject* Set4PyObject_add(PyObject* self, PyObject* args){
    PyObject *stCapsule, *x;
    PARSE_ARGS("OO", &stCapsule, &x);
    Set4PyObject* st = GET_POINTER(stCapsule);
    bool res = st->add(x);
    return Py_BuildValue("O", res ? Py_True : Py_False);
}
PyObject* Set4PyObject_remove(PyObject* self, PyObject* args){
    PyObject *stCapsule, *x;
    PARSE_ARGS("OO", &stCapsule, &x);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->remove(x);
    return Py_BuildValue("O", res);
}
PyObject* Set4PyObject_search_higher_equal(PyObject* self, PyObject* args){
    PyObject *stCapsule, *x;
    PARSE_ARGS("OO", &stCapsule, &x);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->search_higher_equal(x);
    return Py_BuildValue("O", res);
}
PyObject* Set4PyObject_min(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    PARSE_ARGS("O", &stCapsule);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->min();
    return Py_BuildValue("O", res);
}
PyObject* Set4PyObject_max(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    PARSE_ARGS("O", &stCapsule);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->max();
    return Py_BuildValue("O", res);
}
PyObject* Set4PyObject_pop_min(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    PARSE_ARGS("O", &stCapsule);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->pop_min();
    return res;  // 参照カウントを増やさない
}
PyObject* Set4PyObject_pop_max(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    PARSE_ARGS("O", &stCapsule);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->pop_max();
    return res;  // 参照カウントを増やさない
}
PyObject* Set4PyObject_len(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    PARSE_ARGS("O", &stCapsule);
    Set4PyObject* st = GET_POINTER(stCapsule);
    size_t res = st->len();
    return Py_BuildValue("l", (long)res);
}
PyObject* Set4PyObject_next(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    PARSE_ARGS("O", &stCapsule);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->iter_next();
    return Py_BuildValue("O", res);
}
PyObject* Set4PyObject_prev(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    PARSE_ARGS("O", &stCapsule);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->iter_prev();
    return Py_BuildValue("O", res);
}
PyObject* Set4PyObject_to_list(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    PARSE_ARGS("O", &stCapsule);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->to_list();
    return res;  // 参照カウントを増やさない
}
PyObject* Set4PyObject_get(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    PARSE_ARGS("O", &stCapsule);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->get();
    return Py_BuildValue("O", res);
}
PyObject* Set4PyObject_erase(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    PARSE_ARGS("O", &stCapsule);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->erase();
    return Py_BuildValue("O", res);
}
PyObject* Set4PyObject_copy(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    PARSE_ARGS("O", &stCapsule);
    Set4PyObject* st = GET_POINTER(stCapsule);
    Set4PyObject* st2 = new Set4PyObject(*st);
    return PyCapsule_New((void*)st2, "Set4PyObjectPtr", Set4PyObject_free);
}
PyObject* Set4PyObject_getitem(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    long idx;
    PARSE_ARGS("Ol", &stCapsule, &idx);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->getitem(idx);
    return Py_BuildValue("O", res);
}
PyObject* Set4PyObject_pop(PyObject* self, PyObject* args){
    PyObject *stCapsule;
    long idx;
    PARSE_ARGS("Ol", &stCapsule, &idx);
    Set4PyObject* st = GET_POINTER(stCapsule);
    PyObject* res = st->pop(idx);
    return res;  // 参照カウントを増やさない
}
PyObject* Set4PyObject_index(PyObject* self, PyObject* args){
    PyObject *stCapsule, *x;
    PARSE_ARGS("OO", &stCapsule, &x);
    Set4PyObject* st = GET_POINTER(stCapsule);
    long res = st->index(x);
    return Py_BuildValue("l", res);
}
static PyMethodDef SetMethods[] = {
    {"construct", Set4PyObject_construct, METH_VARARGS, "Create set object"},
    {"construct_from_list", Set4PyObject_construct_from_list, METH_VARARGS, "Create set object from list"},
    {"add", Set4PyObject_add, METH_VARARGS, "Add item"},
    {"remove", Set4PyObject_remove, METH_VARARGS, "Remove item"},
    {"search_higher_equal", Set4PyObject_search_higher_equal, METH_VARARGS, "Search item"},
    {"min", Set4PyObject_min, METH_VARARGS, "Get minimum item"},
    {"max", Set4PyObject_max, METH_VARARGS, "Get maximum item"},
    {"pop_min", Set4PyObject_pop_min, METH_VARARGS, "Pop minimum item"},
    {"pop_max", Set4PyObject_pop_max, METH_VARARGS, "Pop maximum item"},
    {"len", Set4PyObject_len, METH_VARARGS, "Get size"},
    {"next", Set4PyObject_next, METH_VARARGS, "Get next value"},
    {"prev", Set4PyObject_prev, METH_VARARGS, "Get previous value"},
    {"to_list", Set4PyObject_to_list, METH_VARARGS, "Make list from set"},
    {"get", Set4PyObject_get, METH_VARARGS, "Get item that iterator is pointing at"},
    {"erase", Set4PyObject_erase, METH_VARARGS, "Erase item that iterator is pointing at"},
    {"copy", Set4PyObject_copy, METH_VARARGS, "Copy set"},
    {"getitem", Set4PyObject_getitem, METH_VARARGS, "Get item by index"},
    {"pop", Set4PyObject_pop, METH_VARARGS, "Pop item"},
    {"index", Set4PyObject_index, METH_VARARGS, "Get index of item"},
    {NULL, NULL, 0, NULL} 
};

static struct PyModuleDef setmodule = {
    PyModuleDef_HEAD_INIT,
    "cppset", 
    NULL, 
    -1, 
    SetMethods,
};

PyMODINIT_FUNC PyInit_cppset(void){
    return PyModule_Create(&setmodule);
}
"""
code_setup = r"""
from distutils.core import setup, Extension
module = Extension(
    "cppset",
    sources=["set_wrapper.cpp"],
    extra_compile_args=["-O3", "-march=native"]
)
setup(
    name="SetMethod",
    version="0.1.0",
    description="wrapper for C++ set",
    ext_modules=[module]
)
"""

import os
import sys
if sys.argv[-1] == "ONLINE_JUDGE" or os.getcwd() != "/imojudge/sandbox":
    with open("set_wrapper.cpp", "w") as f:
        f.write(code_cppset)
    with open("setup.py", "w") as f:
        f.write(code_setup)
    os.system(f"{sys.executable} setup.py build_ext --inplace")


import cppset
class CppSet:
    def __init__(self, lst=None, capsule=None):
        if lst:
            self.st = cppset.construct_from_list(lst)
        elif capsule:
            self.st = capsule
        else:
            self.st = cppset.construct()

    def add(self, val):
        return cppset.add(self.st, val)

    def remove(self, val):
        return cppset.remove(self.st, val)

    def search_higher_equal(self, val):
        return cppset.search_higher_equal(self.st, val)

    def min(self):
        return cppset.min(self.st)

    def max(self):
        return cppset.max(self.st)

    def pop_min(self):
        return cppset.pop_min(self.st)

    def pop_max(self):
        return cppset.pop_max(self.st)

    def __len__(self):
        return cppset.len(self.st)

    def __getitem__(self, idx):
        # g++ 拡張
        return cppset.getitem(self.st, idx)

    def pop(self, idx):
        # g++ 拡張
        return cppset.pop(self.st, idx)

    def index(self, val):
        # g++ 拡張  # イテレータは変化しない
        return cppset.index(self.st, val)

    def __contains__(self, val):
        return self.search_higher_equal(val) == val

    def next(self):
        return cppset.next(self.st)

    def prev(self):
        return cppset.prev(self.st)

    def to_list(self):
        return cppset.to_list(self.st)

    def get(self):
        return cppset.get(self.st)

    def erase(self):
        return cppset.erase(self.st)

    def copy(self):
        return CppSet(capsule=cppset.copy(self.st))

    def __repr__(self):
        return f"CppSet({self.to_list().__repr__()})"

N = int(input())
a = list(map(int,input().split()))
fsum = 0
bsum = 0
fS = CppSet()
bS = CppSet()
fmax = []
bmin = []
for i in range(N):
    fsum += a[i]
    fS.add(a[i])
    bsum += a[3*N-1-i]
    bS.add(a[3*N-1-i])
fmax.append(fsum)
bmin.append(bsum)
for i in range(N,2*N):
    fsum += a[i]
    fS.add(a[i])
    fsum -= fS.pop_min()
    fmax.append(fsum)
    bsum += a[3*N-1-i]
    bS.add(a[3*N-1-i])
    bsum -= bS.pop_max()
    bmin.append(bsum)
bmin = bmin[::-1]
ans = -10**15
for i in range(N+1):
    ans = max(ans,fmax[i]-bmin[i])
print(ans)

Submission status: Accepted

Solution code:
import heapq

N=int(input())
array=[int(x) for x in input().split()]
leftsidesum=[]
firstN=[]
for i in range(N):
	heapq.heappush(firstN,array[i])
summ=sum(firstN)
leftsidesum.append(summ)

for i in range(N,2*N):
	summ+=array[i]
	heapq.heappush(firstN,array[i])
	summ-=heapq.heappop(firstN)
	leftsidesum.append(summ)
	
rightsidesum=[]
secondN=[]
for i in range(3*N-1,2*N-1,-1):
	heapq.heappush(secondN,-array[i])
summm=sum(secondN)
rightsidesum.append(-summm)

for i in range(2*N-1,N-1,-1):
	summm-=array[i]
	heapq.heappush(secondN,-array[i])
	summm-=heapq.heappop(secondN)
	rightsidesum.append(-summm)

	
rightsidesum=rightsidesum[::-1]
tobeprinted=[]
for i in range(N+1):
	tobeprinted.append(leftsidesum[i]-rightsidesum[i])
print(max(tobeprinted))

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """
        (a0+a1+...+ai < x となる最大の i (存在しない時は -1 ) , その時の a0+a1+...+ai )
        a0+a1+...+ai <= x としたい場合は equal = True
        二分探索であるため、ai>=0 を満たす必要がある
        """
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i+1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

####################################################################################################

class BitImos:
    def __init__(self, n):
        self.n = n
        self.p = Bit(self.n + 1)
        self.q = Bit(self.n + 1)

    def add(self, s, t, x):
        """ 区間は閉区間 [s,t] で与えられる。原理は Imos法 と同じ。"""
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def sum(self, s, t):
        """ 半閉区間[s,t)の累積和を与える """
        return self.p.sum(t) + self.q.sum(t) * t - self.p.sum(s) - self.q.sum(s) * s

    def __getitem__(self, s):
        """ 区間加算後の s 番目の要素をO(log N)で取り出す。Imos法だとこの操作にO(N)かかる。"""
        return self.q.sum(s+1)      # sum は半開区間総和なので、s までの和を得るには s+1 としなければならない点に注意

    def __iter__(self):
        """ max(self) で普段 Imos法 でやってることが出来る。"""
        for t in range(self.n):
            yield self.q.sum(t+1)

    def __str__(self):
        text1 = " ".join(["element: "] + list(map(str, self)))
        return text1

####################################################################################################

class BitSet:

    """ 挿入、削除、k番目の値を取得、全てがO(logN)で可能。重複にも対応。"""
    """ 原理的に ai>=0 であるため、二分探索が可能である点も重要　　　　　"""
    def __init__(self, n, A=[]):
        """
        :param n: Aの要素の最大値
        :param A:
        self.size: BitSetに含まれている要素の個数
        """
        self.n = n
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(x, 1)
        self.size += 1
        self.flip += self.size - self.p.sum(x+1)        # 転倒数を使わないなら消してOK

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def order(self,x):
        """
        x が小さい順で何番目かを取得（1-indexed)
        BIT.order(x) = bisect_left(BIT.sort(),x) + 1
        BIT.minimum(BIT.order(x)) = BIT.lower_bound(x) = Aに含まれる x 以上の最小の要素
        """
        return self.p.sum(x) + 1

    def bisect_left(self,x):
        if x <= self.n:
            return self.p.sum(x)
        else:
            return self.size

    def bisect_right(self,x):
        x += 1
        if x <= self.n:
            return self.p.sum(x)
        else:
            return self.size

    def flip_counter(self):
        return self.flip

    def count(self,x):
        return self.p[x]

    def minimum(self,k=1):
        """ k 番目に小さい値を取得 （1-indexed）  """
        if k <= self.size:
            return self.p.lower_bound(k)[0] + 1
        else:
            sys.stderr.write("minimum: list index out of range (k={0})\n".format(k))

    def min(self):
        return self.minimum(1)

    def max(self):
        return self.p.lower_bound(self.size)[0] + 1

    def upper_bound(self,x):
        """ x以下の最大の要素の値を返す """
        k = self.p.sum(x+1)
        if k:
            return self.minimum(k)
        else:
            sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x))

    def lower_bound(self,x):
        """ x以上の最小の要素の値を返す """
        k = self.p.sum(x) + 1
        if k <= self.size:
            return self.minimum(k)
        else:
            sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x))

    def __getitem__(self, k):
        """
        元のリストをソートしたリストの k 番目の要素 (0-indexed)
        B[k] = sorted(A)[k]
        """
        if k >= 0:
            return self.minimum(k+1)
        else:
            return self.minimum(self.size + 1 + k)

    def __len__(self):
        return self.size

    def __iter__(self):
        for i in range(self.n+1):
            if self.p[i]:
                for _ in range(self.p[i]):
                    yield i

    def __str__(self):
        text1 = " ".join(list(map(str, self)))
        return "[" + text1 + "]"

####################################################################################################

class BitSet2:
    """ 座標圧縮が必要な場合 """
    def __init__(self, data, A=[]):
        """
        self.size: BitSetに含まれている要素の個数
        """
        """ BitSetに入り得る値を先読みした物を data に格納 """
        self.data = sorted(list(set(data)))
        self.n = len(self.data)
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        self.code = {}
        self.decode = {}
        for i, b in enumerate(self.data):
            self.code[b] = i
            self.decode[i] = b
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(self.code[x], 1)
        self.size += 1
        self.flip += self.size - self.p.sum(self.code[x]+1)        # 転倒数を使わないなら消してOK

    def remove(self,x):
        self.p.add(self.code[x], -1)
        self.size -= 1

    def order(self,x):
        """
        x が小さい順で何番目かを取得（1-indexed)
        BIT.order(x) = bisect_left(BIT.sort(),x) + 1
        BIT.minimum(BIT.order(x)) = BIT.lower_bound(x) = Aに含まれる x 以上の最小の要素
        """
        if x in self.code.keys():
            return self.p.sum(self.code[x]) + 1
        else:
            return self.p.sum(bisect_right(self.data, x)) + 1

    def bisect_left(self,x):
        if x in self.code.keys():
            return self.p.sum(self.code[x])
        else:
            return self.p.sum(bisect_right(self.data, x))

    def bisect_right(self,x):
        x += 1
        if x in self.code.keys():
            return self.p.sum(self.code[x])
        else:
            return self.p.sum(bisect_right(self.data, x))

    def count(self,x):
        return self.p[self.code[x]]

    def minimum(self,k=1):
        """ k 番目に小さい値を取得 """
        if k <= self.size:
            return self.decode[self.p.lower_bound(k)[0] + 1]
        else:
            sys.stderr.write("minimum: list index out of range (k={0})\n".format(k))

    def min(self):
        return self.minimum(1)

    def max(self):
        return self.decode[self.p.lower_bound(self.size)[0] + 1]

    def upper_bound(self,x):
        """ x以下の最大の要素の値を返す """
        if x in self.code.keys():
            y = self.code[x] + 1
        else:
            y = bisect_right(self.data, x)
        k = self.p.sum(y)
        if k:
            return self.minimum(k)
        else:
            sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x))

    def lower_bound(self,x):
        """ x以上の最小の要素の値を返す """
        if x in self.code.keys():
            y = self.code[x]
        else:
            y = bisect_left(self.data, x)
        k = self.p.sum(y) + 1
        if k <= self.size:
            return self.minimum(k)
        else:
            sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x))

    def __getitem__(self, k):
        """
        元のリストをソートしたリストの k 番目の要素 (0-indexed)
        B[k] = sorted(A)[k]
        """
        if k >= 0:
            return self.minimum(k+1)
        else:
            return self.minimum(self.size + 1 + k)

    def __len__(self):
        return self.size

    def __iter__(self):
        for i in range(self.n+1):
            if self.p[i]:
                for _ in range(self.p[i]):
                    yield self.decode[i]

    def __str__(self):
        """ 配列をソートされた形で表示 """
        text1 = " ".join(list(map(str, self)))
        return "[" + text1 + "]"

#######################################################################

import sys
input = sys.stdin.readline
from bisect import bisect_left
from bisect import bisect_right
from heapq import *
N = int(input())
A = list(map(int, input().split()))
P = []
for a in A[:N]: heappush(P,a)
B = A[N:]
Q = BitSet2(B,B)
S2=sum(sorted(B)[:N])
S1=sum(A[:N])
res = S1-S2
for i in range(N):
    a = A[N+i]
    p = heappop(P)
    S1 += max(a - p, 0)
    heappush(P,max(a,p))
    q = Q[N-1]
    Q.remove(a)
    if a <= q:
        S2 += Q[N-1]-a
    res = max(S1-S2,res)
print(res)

Submission status: Accepted

Solution code:
import heapq

N = int(input())
an = list(map(int, input().split()))

left = [0] * (N+1)
right = [0] * (N+1)

left[0] = sum(an[:N])
right[-1] = -sum(an[2*N:])

l = an[:N]
heapq.heapify(l)
m = an[N:2*N]
r = [-i for i in an[2*N:]]
heapq.heapify(r)

for k in range(N):
    heapq.heappush(l, m[k])
    left[1+k] = left[k] + m[k] - heapq.heappop(l)

    heapq.heappush(r, -m[-1-k])
    right[-2-k] = right[-1-k] - heapq.heappop(r) - m[-1-k]

ans = -float('inf')
for i in range(N+1):
    ans = max(ans, left[i]+right[i])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import heapq
import copy

N = int(input())
an = list(map(int, input().split()))

ans = sum(an[:N]) - sum(an[2*N:])
left = [0] * (N+1)
right = [0] * (N+1)
left[0] = sum(an[:N])
right[-1] = -sum(an[2*N:])

l = an[:N]
heapq.heapify(l)
m = an[N:2*N]
r = [-i for i in an[2*N:]]
heapq.heapify(r)

for k in range(N):
    heapq.heappush(l, m[k])
    left[1+k] = left[k] + m[k] - heapq.heappop(l)

    heapq.heappush(r, -m[-1-k])
    right[-2-k] = right[-1-k] - heapq.heappop(r) - m[-1-k]

ans = float('-inf')
for i in range(N+1):
    ans = max(ans, left[i]+right[i])


print(ans)

Submission status: Accepted

Solution code:
import heapq

def main():
    N = int(input())
    A = list(map(int, input().split()))
    s = A[:N]

    t = A[2*N:]
    t = [-1*x for x in t]
    heapq.heapify(s)
    heapq.heapify(t)
    n = [0] * (N+1)
    m = [0] * (N+1)
    n[0] = sum(s)
    m[N] = - sum(t)
    for k in range(1, N+1):
        tmp = A[N-1+k]
        a = heapq.heappushpop(s, tmp)
        n[k] = n[k-1] + tmp - a

    for k in range(N-1, -1, -1):
        tmp = - A[N+k]
        a = heapq.heappushpop(t, tmp)
        m[k] = m[k+1] - tmp + a
    ans = -float("inf")
    for k in range(N+1):
        ans = max(ans, n[k]-m[k])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
N=int(input())
A=list(map(int, input().split()))
A_rev = [-x for x in A[::-1]] #逆順にして各要素を-1倍する
left, right = A[:N], A_rev[:N]
sum_left_list, sum_right_list = [0]*(N+1), [0]*(N+1)
sum_left, sum_right = sum(left), sum(right)
sum_left_list[0], sum_right_list[0]=sum_left, sum_right
heapq.heapify(left)
heapq.heapify(right)
#left: k=N, N+1,..., 2N-1まで動かして大きい方からN個の和を求める
for k in range(N, 2*N):
	val=A[k]
	heapq.heappush(left, val)
	min_val = heapq.heappop(left)
	sum_left += val
	sum_left -= min_val
	sum_left_list[k-N+1] = sum_left

#right: k=N, N+1,..., 2N-1まで動かして大きい方からN個の和を求める
for k in range(N, 2*N):
	val = A_rev[k]
	heapq.heappush(right, val)
	min_val = heapq.heappop(right)
	sum_right += val
	sum_right -= min_val
	sum_right_list[k-N+1] = sum_right
sum_right_list=sum_right_list[::-1]

ans=-float("inf")
for i in range(N+1):
	ans=max(ans, sum_left_list[i]+sum_right_list[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq as hp
input = sys.stdin.readline
N= int(input())
A = list(map(int,input().split()))

l = A[:N]
r = [-a for a in A[2*N:]]
hp.heapify(l)
hp.heapify(r)
L = sum(l)
R = sum(r)

Lcand = [L]
Rcand = [R]
for a in A[N:2*N]:
    if l[0] < a:
        L += a - l[0]
        hp.heappushpop(l,a)
    Lcand.append(L)

for a in A[N:2*N][::-1]:
    if r[0] < -a:
        R += -a - r[0]
        hp.heappushpop(r,-a)
    Rcand.append(R)

print(max([l+r for l,r in zip(Lcand, Rcand[::-1])]))

Submission status: Accepted

Solution code:
import heapq 

N=int(input())
A=list(map(int,input().split()))

A1,A2,A3=A[:N],A[N:2*N],A[2*N:]

res=[]
qA=A1
heapq.heapify(qA)
sumA=sum(qA)

qB=[-b for b in A3]
heapq.heapify(qB)
sumB=sum(qB)


resA,resB=[sumA],[sumB]
for k in range(N):
    heapq.heappush(qA,A2[k])
    a=heapq.heappop(qA)
    sumA+=A2[k]-a
    
    heapq.heappush(qB,-A2[N-(k+1)])
    b=heapq.heappop(qB)
    sumB+=-A2[N-(k+1)]-b
    resA.append(sumA)
    resB.append(sumB)

res=[resA[i]+resB[N-i] for i in range(N+1)]
print(max(res))

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))

import heapq
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        return heapq.heappop(self.hq) * self.sign
 
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self): #popせずに見るだけ
        return self.hq[0] * self.sign
    
hq=Heapq(A[:n]) ; L=[0]*(n+1) ; L[0]=sum(A[:n])
hq2=Heapq(A[2*n:],1) ; R=[0]*(n+1) ; R[-1]=sum(A[n*2:])
ans=-2**62
for i in range(n,2*n):
    ku= hq.pop()
    ire= max(ku, A[i])
    L[i-n+1]= L[i-n]+ire-ku
    hq.push(ire)
    #
    ku=hq2.pop()
    ire= min(ku,A[-i-1])
    R[-(i-n+2)]= R[-(i-n+1)]+ire-ku
    hq2.push(ire)
#print(L,R)
for i in range(n+1):
    ans=max(ans, L[i]-R[i])
print(ans)