結果

問題 No.506 限られたジャパリまん
ユーザー rpy3cpp
提出日時 2017-04-23 00:59:45
言語 Python3
(3.7.4 + numpy 1.14.5 + scipy 1.1.0)
結果
AC  
実行時間 338 ms
コード長 1,300 Byte
コンパイル時間 52 ms
使用メモリ 5,636 KB
最終ジャッジ日時 2019-09-20 00:43:19

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 19 ms
5,632 KB
2.txt AC 18 ms
5,628 KB
3.txt AC 19 ms
5,632 KB
4.txt AC 19 ms
5,632 KB
5.txt AC 41 ms
5,632 KB
6.txt AC 38 ms
5,636 KB
7.txt AC 19 ms
5,628 KB
8.txt AC 21 ms
5,632 KB
9.txt AC 338 ms
5,632 KB
10.txt AC 176 ms
5,628 KB
11.txt AC 23 ms
5,636 KB
12.txt AC 314 ms
5,628 KB
13.txt AC 196 ms
5,628 KB
14.txt AC 18 ms
5,628 KB
15.txt AC 21 ms
5,632 KB
16.txt AC 19 ms
5,628 KB
17.txt AC 266 ms
5,632 KB
18.txt AC 28 ms
5,632 KB
19.txt AC 37 ms
5,632 KB
20.txt AC 64 ms
5,632 KB
21.txt AC 95 ms
5,632 KB
22.txt AC 45 ms
5,632 KB
23.txt AC 122 ms
5,636 KB
24.txt AC 75 ms
5,628 KB
25.txt AC 43 ms
5,636 KB
テストケース一括ダウンロード

ソースコード

diff #
def read_data():
    H, W, K, P = map(int, input().split())
    xys = []
    names = []
    for k in range(K):
        x, y, name = input().rstrip().split()
        xys.append((int(x), int(y)))
        names.append(name)
    return H, W, K, P, xys, names

def solve(H, W, K, P, xys, names):
    record = 0
    sol_mask = 0
    mapp = [[1] * (W + 1) for _ in range(H + 1)]
    for mask in range(1 << K):
        score = calc_score(mask, mapp, H, W, K, P, xys)
        if score > record:
            record = score
            sol_mask = mask
    print_result(record, sol_mask, names)

def print_result(record, sol_mask, names):
    print(record % (10**9 + 7))
    if record:
        for i in range(len(names)):
            if (sol_mask & 1) == 0:
                print(names[i])
            sol_mask >>= 1

def calc_score(mask, mapp, H, W, K, P, xys):
    if bin(mask).count('1') != K - P:
        return 0
    pos = [i for i in range(K) if mask & (1 << i)]
    for p in pos:
        x, y = xys[p]
        mapp[x][y] = 0
    dp = [1] + [0] * (W + 1)
    for row in mapp:
        for y, c in enumerate(row):
            dp[y] = (dp[y] + dp[y - 1]) * c
    for p in pos:
        x, y = xys[p]
        mapp[x][y] = 1
    return dp[W]


H, W, K, P, xys, names = read_data()
solve(H, W, K, P, xys, names)

0