Problem:


Problem F: The Castle

待ち伏せていた敵を見事撃破したうさぎは, 主人公を敵の城内に進めることに成功した. 主人公が城の地下牢に捕らわれていたねこたちを解放したところ, 彼らのうちの何匹かが主人公の力になってくれることになった.

ねこたちの話では, 城の奥にいる魔王に辿りつくには1 番からn 番のn 個の部屋をこの順に通り抜けることになるが, 各部屋には1 体ずつ敵が待ち受けていて逐一倒していかなければならないという. 仲間になったm匹のねこそれぞれについて, 各部屋の敵それぞれに対する勝率が分かっており, 主人公はこのねこたちを1 匹ずつ城の奥へ向けて派遣する. 各部屋はそこにいる敵を倒してからでなければ通過できないので, あるねこがある部屋の敵にやられたら, 次のねこはその部屋の敵から戦っていくことになる.

派遣されたねこは敵にやられるまで進むが, 派遣したねこがどの部屋の敵にやられたかは毎回知ることができ, それによって次にどのねこを派遣するかを決めることができる. どのようにすれば, ねこたちが待ち受けるすべての敵を倒せる確率が最大になるだろうか.

Input

入力の一行目にはm とn がスペースで区切られて与えられる. 1 ≤ m, n ≤ 16

つづくm 行には, 猫が敵に勝つ確率を表すn 個の実数が与えられる. i + 1 行目のj 個目の実数は, j 番の部屋の敵に勝つ確率を表している. 確率は小数点以下3 桁まで.

Output

ねこたちが待ち受けるすべての敵を倒せる確率が最大になるようにうまく順番を決めていくとき, その確率を答えよ. 出力は誤差を含んでいてもよいが, 真の値との誤差は10−9 以内にせよ.

Sample Input 1

2 3
0.900 0.500 0.100
0.500 0.500 0.500

Sample Output 1

0.372500000000



Sample input:
2 3
0.900 0.500 0.100
0.500 0.500 0.500


Sample output:
0.372500000000

Submission status: Accepted

Solution code:
import sys
def solve():
    readline = sys.stdin.buffer.readline
    write = sys.stdout.buffer.write
    M, N = map(int, readline().split())
    P = [list(map(float, readline().split())) + [0] for i in range(M)]
    M2 = (1 << M)
    dp = [[0]*(N+1) for i in range(M2)]
    dp[0][N] = 1
    for state in range(1, M2):
        dps = dp[state]
        for k in range(M):
            if state & (1 << k) == 0:
                continue
            pk = P[k]
            dpk = dp[state ^ (1 << k)]
            s = 0
            for i in range(N, -1, -1):
                s += dpk[i] * (1 - pk[i])
                dps[i] = max(dps[i], s)
                s *= pk[i-1]
    write(b"%.16f\n" % dp[M2-1][0])
solve()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n,m):
        a = [LF() for _ in range(n)]
        b = []
        mx = 1 << n
        for i in range(mx):
            t = []
            for j in range(n):
                if i & (1<<j):
                    t.append(j)
            b.append(t)

        nmx = n * mx
        ca = [1] * nmx
        cn = [c<<n for c in range(n)]
        ci = [1<<c for c in range(n)]
        for k in range(1,m+1):
            ka = [a[c][-k] for c in range(n)]
            na = [0] * nmx
            re = [0] * mx
            for x in range(1,mx):
                for c in b[x]:
                    y = cn[c] + x
                    na[y] = ka[c] * ca[y] + (1 - ka[c]) * re[x - ci[c]]
                    if re[x] < na[y]:
                        re[x] = na[y]
            ca = na

        return '{:0.10f}'.format(max(ca))

    while 1:
        n,m = LI()
        if n == 0:
            break
        rr.append(f(n,m))
        break

    return '\n'.join(map(str, rr))


print(main())