結果

問題 No.309 シャイな人たち (1)
ユーザー tjake
提出日時 2015-12-02 15:55:02
言語 Python2
(2.7.18)
結果
TLE  
実行時間 -
コード長 1,616 bytes
コンパイル時間 481 ms
コンパイル使用メモリ 6,912 KB
実行使用メモリ 17,024 KB
最終ジャッジ日時 2024-09-14 07:56:31
合計ジャッジ時間 10,602 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import product

inputs = lambda:map(int, raw_input().split())
r, c = inputs()
raw_input()
p = [inputs() + [0] for i in xrange(r)] + [0]*(c+1)
raw_input()
s = [inputs() + [4] for i in xrange(r)] + [4]*(c+1)

dp = [[0]*(2**c) for i in xrange(r+1)]

def bit_get(v, i):
    if i<0: return 0
    return (v>>i) & 1

def f(a, b, c):
    r  = pp[j] if a else 100-pp[j]
    r *= pi[j-1] if b else 100-pi[j-1]
    r *= pi[j+1] if c else 100-pi[j+1]
    return r/1000000.0

dp[0][0] = 1.

ans = 0

for i in xrange(r):
    sp = s[i-1]
    si = s[i]
    pp = s[i]
    pi = p[i]
    dpp = dp[i]
    dpi = dp[i+1]
    for S in xrange(2**c):
        if dpp[S]==0.0:
            continue
        for T in xrange(2**c):
            res = dpp[S]
            for j in xrange(c):
                if si[j]==0:
                    res *= (pi[j] if bit_get(T, j) else 100-pi[j])/100.0
                else:
                    x, y, z = bit_get(S, j), bit_get(T, j-1), bit_get(T, j+1)
                    #print i, bin(S), bin(T)
                    #print x, y, z, f(x, y, z)
                    if x+y+z >= si[j]:
                        #res *= (pi[j] if bit_get(T, j) else 100-pi[j])*f(x, y, z)/100.0
                        res *= (pi[j] if bit_get(T, j) else 100-pi[j])/100.0
                    else:
                        if bit_get(T, j):
                            res = 0.0
                            break
            dpi[T] += res
            #print bin(T), res
        #print i, "result"
    for T in xrange(2**c):
        #print bin(T), dpi[T]
        ans += bin(T).count("1") * dpi[T]
#print dp
print ans
0