Problem Brief

Efficient Deployments 🌨️

INTERNOA

See Snowflake online assessment and hiring insights

A supercomputer has several processors to deploy for execution. They are arranged sequentially in a row from 1 to n. The efficiency of each processor depends upon the order of deployment of its adjacent processors.

For the i^th processor, the efficiency of the i^th processor is no_adjacent[i], one_adjacent[i], or both_adjacent[i] when neither, one, or both adjacent processors is deployed before processor i.

Note: The 1^st and n^th processors can only have one adjacent.

Find the maximum possible sum of efficiencies amongst all possible orders of deployment.

Function Description

Complete the function maxEfficiency in the editor.

maxEfficiency has the following parameters:

int noAdjacent[n]: an array of integers

int oneAdjacent[n]: an array of integers

int bothAdjacent[n]: an array of integers

Returns

long_int: the maximum possible sum of efficiencies

1Example 1

Input

noAdjacent = [1, 2, 3, 4], oneAdjacent = [4, 4, 2, 1], bothAdjacent = [0, 1, 1, 0]

Output

Explanation

Consider the following orders of deployment (1-based indexing):

The deployment sequence is {1 → 3 → 4 → 2}. Then, the sum of efficiencies = no_adjacent[1] + no_adjacent[3] + one_adjacent[4] + both_adjacent[2] = 1 + 3 + 1 + 1 = 6.

Let the deployment sequence be {4 → 2 → 1 → 3}, no_adjacent[4] + no_adjacent[2] + one_adjacent[1] + both_adjacent[3] = 4 + 2 + 4 + 1 = 11.

Let the deployment sequence be {4 → 3 → 2 → 1}, one_adjacent[3] + one_adjacent[2] + 2 + 2 + 4 + 1 = 7.

Similarly, other deployment orders can be performed.

Amongst all possible deployments, the maximum possible sum of efficiencies is 13.

2Example 2

Input

noAdjacent = [2, 1, 3], oneAdjacent = [4, 2, 1], bothAdjacent = [1, 2, 3]

Output

Explanation

Several ways to deploy processors are:

let dethe deployment sequence be {1 -> 2 -> 3}

* The sum of efficiencies = no_adjacent[1] + one_adjacent[2] ++ 2 + 1 = 5

{1 -> 3 -> 2_, no_adjacent[1] + no_adjacent[3] + both_adjacent[2] = 2 + 3 + 2 = 7

{2 -> 1 -> 3}, no_adjacent[2] + one_adjacent[1] ++ 4 + 1 = 6

{2 -> 3 -> 1}, no_adjacent[2] + one_adjacent[3] ++ 1 + 4 = 6

{3 -> 2 -> 1}, no_adjacent[3] + one_adjacent[2] ++ 2 + 4 = 9

{3 -> 1 -> 2}, no_adjacent[3] + no_adjacent[1] + both_adjacent[2] = 3 + 2 + 2 = 7

3Example 3

Input

noAdjacent = [1, 6], oneAdjacent = [2, 3], bothAdjacent = [3, 2]

Output

Explanation

Some ways to deploy processors are:

Let the deployment sequence be {1 -> 2}. Then, sum of efficiencies = no_adjacent[1] ++ 3 = 4

{2 -> 1}, no_adjacent[2] ++ 2 = 8

Constraints

Limits and guarantees your solution can rely on.

1 <= n <= 10⁵

1 <= no_adjacent[i], one_adjacent[i], both_adjacent[i] <= 10⁹