ARC 074 D - 3N Numbers

D - 3N Numbers

要素数3Nの数列からN個の要素を取り除き、前からN個の合計から後ろのN個の合計を引き、それを最大化したい

解法
左から大きい数をN個選び、右から小さい数をN個選びたい。この時左から選んだ物は全て右のものより左にある。
よって境界ができる。境界を全通り試せば答えがわかる。

問題の芯
なにかしらの値を定めて、簡単な問題に分割する

public static void main(String[] args)
    {
        N = sc.nextInt();
        A = sc.nextLongArray(3 * N);
        PriorityQueue<Long> pr = new PriorityQueue<>();
        PriorityQueue<Long> pr2 = new PriorityQueue<>(new ReverseComparator());
        long lmax[] = new long[N + 1];
        for (int i = 0; i < N; i++)
        {
            pr.add(A[i]);
            lmax[0] += A[i];
        }
        for (int i = N; i < 2 * N; i++)
        {
            pr.add(A[i]);
            lmax[i - N + 1] = lmax[i - N];
            lmax[i - N + 1] += A[i];
            lmax[i - N + 1] -= pr.poll();
        }


        long rmax[] = new long[N + 1];
        for (int i = 3 * N - 1; i >= 2 * N; i--)
        {
            pr2.add(A[i]);
            rmax[0] += A[i];
        }
        for (int i = 2 * N - 1; i >= N; i--)
        {
            pr2.add(A[i]);
            rmax[(2 * N - 1) - i + 1] = rmax[(2 * N - 1) - i];
            rmax[(2 * N - 1) - i + 1] += A[i];
            rmax[(2 * N - 1) - i + 1] -= pr2.poll();
        }

        long maxr = Long.MIN_VALUE;
        for (int i = 0; i < N+1; i++)
        {
            maxr = Math.max(maxr, lmax[i]-rmax[N-i]);
        }
        System.out.println(maxr);

    }