The rules of Sith Tournament are well known to everyone. n Sith take part in the Tournament. The Tournament starts with the random choice of two Sith who will fight in the first battle. As one of them loses, his place is taken by the next randomly chosen Sith who didn't fight before. Does it need to be said that each battle in the Sith Tournament ends with a death of one of opponents? The Tournament ends when the only Sith remains alive.

Jedi Ivan accidentally appeared in the list of the participants in the Sith Tournament. However, his skills in the Light Side of the Force are so strong so he can influence the choice of participants either who start the Tournament or who take the loser's place after each battle. Of course, he won't miss his chance to take advantage of it. Help him to calculate the probability of his victory.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 18) — the number of participants of the Sith Tournament.

Each of the next n lines contains n real numbers, which form a matrix p_{ij} (0 ≤ p_{ij} ≤ 1). Each its element p_{ij} is the probability that the i-th participant defeats the j-th in a duel.

The elements on the main diagonal p_{ii} are equal to zero. For all different i, j the equality p_{ij} + p_{ji} = 1 holds. All probabilities are given with no more than six decimal places.

Jedi Ivan is the number 1 in the list of the participants.


-----Output-----

Output a real number — the probability that Jedi Ivan will stay alive after the Tournament. Absolute or relative error of the answer must not exceed 10^{ - 6}.


-----Examples-----
Input
3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0

Output
0.680000000000000

Difficulty: HARD
Tags: Dynamic programming

Bit manipulation

Mathematics

Probability
Skill types: Dynamic programming

Bit manipulation

Starter code:

Solutions:
import sys
n = int(input())
prob = [list(map(float, input().split())) for _ in range(n)]
dp = [[0.0] * n for _ in range(1 << n)]
dp[1][0] = 1.0
for mask in range(3, 1 << n):
	for i in range(n):
		if not mask & 1 << i:
			continue
		for j in range(n):
			if i != j and mask & 1 << j:
				dp[mask][i] = max(dp[mask][i], dp[mask - (1 << j)][i] * prob[i][j] + dp[mask - (1 << i)][j] * prob[j][i])
print(max(dp[-1]))


import sys
import bisect
from bisect import bisect_left as lb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0

def hnbhai(t):
	n = sb()
	p = []
	for i in range(n):
		p.append(sflo())
	dp = [0] * (1 << n)
	dp[1] = 1
	for i in range(2, 1 << n):
		for j in range(1, n):
			for k in range(0, j):
				if i >> j & 1 and i >> k & 1:
					dp[i] = max(dp[i], dp[i ^ 1 << j] * p[k][j] + dp[i ^ 1 << k] * p[j][k])
	print(dp[-1])
for _ in range(1):
	hnbhai(_ + 1)


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	p = [list(map(float, input().split())) for _ in range(n)]
	y = 1 << n
	dp = [[0] * y for _ in range(n)]
	dp[0][y - 1] = 1
	for i in range(y - 2, -1, -1):
		mask = 1
		for j in range(n):
			if not mask & i:
				mask <<= 1
				continue
			mask1 = 1
			for k in range(n):
				if i & mask1:
					mask1 <<= 1
					continue
				dp[j][i] = max(dp[j][i], dp[j][i | mask1] * p[j][k] + dp[k][i | mask1] * p[k][j])
				mask1 <<= 1
			mask <<= 1
	print(max((dp[i][1 << i] for i in range(n))))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()