結果

問題 No.506 限られたジャパリまん
ユーザー rpy3cpp
提出日時 2017-04-23 00:53:37
言語 Python3
(3.7.4 + numpy 1.14.5 + scipy 1.1.0)
結果
WA  
実行時間 -
コード長 1,284 Byte
コンパイル時間 125 ms
使用メモリ 5,644 KB
最終ジャッジ日時 2019-09-20 00:42:48

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 21 ms
5,628 KB
2.txt AC 20 ms
5,624 KB
3.txt AC 21 ms
5,624 KB
4.txt AC 19 ms
5,624 KB
5.txt WA -
6.txt WA -
7.txt RE -
8.txt WA -
9.txt RE -
10.txt RE -
11.txt RE -
12.txt WA -
13.txt WA -
14.txt RE -
15.txt RE -
16.txt WA -
17.txt RE -
18.txt RE -
19.txt WA -
20.txt WA -
21.txt WA -
22.txt WA -
23.txt WA -
24.txt WA -
25.txt AC 43 ms
5,624 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)
    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] * (H + 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[H]


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