結果

問題 No.506 限られたジャパリまん
ユーザー rpy3cpp
提出日時 2017-04-23 00:53:37
言語 Python3
(3.8.1 + numpy 1.14.5 + scipy 1.1.0)
結果
WA  
実行時間 -
コード長 1,284 Byte
コンパイル時間 56 ms
使用メモリ 8,312 KB
最終ジャッジ日時 2020-01-23 23:40:47

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 16 ms
8,272 KB
2.txt AC 16 ms
8,156 KB
3.txt AC 20 ms
8,168 KB
4.txt AC 16 ms
8,232 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 44 ms
8,280 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