Brewing potion 5 - MarisaOJ: Marisa Online Judge

Marisa has

n \times 2

$n \times 2$ mushrooms and she wants to brew

n

$n$ potion bottles, each using exactly 2 mushrooms. If the

i^{t h}

$i^{th}$ mushroom is paired with the

j^{t h}

$j^{th}$ mushroom, the resulting potion has a power of

A_{i, j}

$A_{i,j}$ . Marisa wants to find the combination of mushrooms that maximizes the total power of the

n

$n$ potion bottles. ### Input - The first line contains an integer

n

$n$ . - The next

n \times 2

$n \times 2$ lines,

i

$i$ -th line contains

n \times 2

$n \times 2$ integers

A_{i, j}

$A_{i, j}$ . It is guaranteed that

A_{i, j} = A_{j, i}

$A_{i,j}=A_{j,i}$ . ### Output - Print the maximum total power of

n

$n$ potion bottles. ### Constraints -

1 \leq n \leq 10

$1 \le n \le 10$ . -

0 \leq | A_{i, j} | \leq 10^{6}

$0 \le |A_{i,j}| \le 10^6$ . ### Example Input:

10 - 2 - 20

$1 0 -2 -2 0$

Output:

- 2

$-2$

Bitmask DP
	Binary board
	Travelling Salesman Problem 2
	Brewing potion 5
	Subsequences counting
	Wooden house
	Xiangqi
	Packing
	Permutation counting
	Counting tilings
	Superstring
	Custom keyboard
	Mushroom harvesting III

Topic

Dynamic Programming

Bitmasks

Rating

1200

Solution (0)

Solution