3N Numbers

AtCoder

IDarc074_b

Time2000ms

Memory256MB

Difficulty—

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$ ## Input Input is given from Standard Input in the following format: $N$ $a_1$ $a_2$ $...$ $a_{3N}$ ## Partial Score * In the test set worth $300$ points, $N ≤ 1000$. [samples]

Samples

Input #1

2
3 1 4 1 5 9

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$.

Input #2

1
1 2 3

Output #2

\-1

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

Input #3

3
8 2 2 7 4 6 5 3 8

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$.

API Response (JSON)

{
  "problem": {
    "name": "3N Numbers",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc074_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let $N$ be a positive integer.\nThere 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 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments