Submission #2557907


Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    int n;
    int[] as;

    public static void main(String args[]) {
        new Main().run();
    }

    void run() {
        FastReader sc = new FastReader();
        n = sc.nextInt();
        as = new int[3 * n];
        for (int i = 0; i < 3 * n; i++) {
            as[i] = sc.nextInt();
        }
        solve();
    }

    void solve() {
        PriorityQueue<Integer> former = new PriorityQueue<>();
        PriorityQueue<Integer> latter = new PriorityQueue<>(Collections.reverseOrder());
        long formerSum = 0;
        long latterSum = 0;
        for (int i = 0; i < n; i++) {
            formerSum += (long)as[i];
            former.offer(as[i]);
        }
        for (int i = 2 * n; i < 3 * n; i++) {
            latterSum += (long)as[i];
            latter.offer(as[i]);
        }
        long[] latterSums = new long[n + 1];
        latterSums[n] = latterSum;
        for (int i = 2 * n - 1; i >= n; i--) {
            int max = latter.peek();
            if (max > as[i]) {
                latterSum -= (long)max;
                latterSum += (long)as[i];
                latter.poll();
                latter.offer(as[i]);
            }
            latterSums[i - n] = latterSum;
        }
        long[] formerSums = new long[n + 1];
        formerSums[0] = formerSum;
        for (int i = n; i < 2 * n; i++) {
            int min = former.peek();
            if (min < as[i]) {
                formerSum -= (long)min;
                formerSum += (long)as[i];
                former.poll();
                former.offer(as[i]);
            }
            formerSums[i - n + 1] = formerSum;
        }
        long diff = formerSums[0] - latterSums[0];
        for (int i = 0; i <= n; i++) {
            long tempDiff = formerSums[i] - latterSums[i];
            if (diff < tempDiff) {
                diff = tempDiff;
            }
        }
        System.out.println(diff);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Submission Info

Submission Time
Task D - 3N Numbers
User ynish
Language Java8 (OpenJDK 1.8.0)
Score 500
Code Size 3318 Byte
Status AC
Exec Time 462 ms
Memory 64428 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 300 / 300 200 / 200
Status
AC × 3
AC × 27
AC × 43
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
Subtask 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt
Case Name Status Exec Time Memory
0_00.txt AC 73 ms 21200 KB
0_01.txt AC 69 ms 17492 KB
0_02.txt AC 69 ms 21204 KB
1_00.txt AC 71 ms 20692 KB
1_01.txt AC 72 ms 18132 KB
1_02.txt AC 70 ms 21076 KB
1_03.txt AC 68 ms 21204 KB
1_04.txt AC 71 ms 18260 KB
1_05.txt AC 69 ms 21332 KB
1_06.txt AC 72 ms 18772 KB
1_07.txt AC 73 ms 20820 KB
1_08.txt AC 93 ms 19284 KB
1_09.txt AC 100 ms 18388 KB
1_10.txt AC 97 ms 23380 KB
1_11.txt AC 103 ms 18772 KB
1_12.txt AC 89 ms 18132 KB
1_13.txt AC 94 ms 21460 KB
1_14.txt AC 93 ms 19924 KB
1_15.txt AC 102 ms 20820 KB
1_16.txt AC 85 ms 19668 KB
1_17.txt AC 88 ms 18132 KB
1_18.txt AC 87 ms 16340 KB
1_19.txt AC 88 ms 19540 KB
1_20.txt AC 110 ms 20052 KB
1_21.txt AC 105 ms 21844 KB
1_22.txt AC 94 ms 20052 KB
1_23.txt AC 105 ms 19924 KB
2_00.txt AC 211 ms 41664 KB
2_01.txt AC 269 ms 55968 KB
2_02.txt AC 462 ms 64428 KB
2_03.txt AC 330 ms 61768 KB
2_04.txt AC 353 ms 55772 KB
2_05.txt AC 308 ms 56316 KB
2_06.txt AC 355 ms 56284 KB
2_07.txt AC 247 ms 53588 KB
2_08.txt AC 302 ms 40256 KB
2_09.txt AC 326 ms 41968 KB
2_10.txt AC 347 ms 43816 KB
2_11.txt AC 316 ms 41600 KB
2_12.txt AC 371 ms 59140 KB
2_13.txt AC 372 ms 57628 KB
2_14.txt AC 387 ms 55940 KB
2_15.txt AC 401 ms 58148 KB