結果

問題 No.506 限られたジャパリまん
ユーザー lam6er
提出日時 2025-04-16 16:02:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,537 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,120 KB
実行使用メモリ 86,272 KB
最終ジャッジ日時 2025-04-16 16:08:59
合計ジャッジ時間 3,960 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def compute_paths(mask, friends, H, W):
    blocked = set()
    for i in range(len(friends)):
        if not (mask & (1 << i)):
            x, y, _ = friends[i]
            blocked.add((x, y))
    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[0][0] = 1
    max_s = H + W
    for s in range(1, max_s + 1):
        x_min = max(0, s - W)
        x_max = min(H, s)
        for x in range(x_min, x_max + 1):
            y = s - x
            if y < 0 or y > W:
                continue
            if (x, y) in blocked:
                continue
            total = 0
            if x > 0 and (x-1, y) not in blocked:
                total += dp[x-1][y]
            if y > 0 and (x, y-1) not in blocked:
                total += dp[x][y-1]
            dp[x][y] = total % MOD
    return dp[H][W]

H, W, K, P = map(int, input().split())
friends = []
for _ in range(K):
    parts = input().split()
    x = int(parts[0])
    y = int(parts[1])
    name = parts[2]
    friends.append((x, y, name))

max_count = -1
best_mask = 0

for mask in range(0, 1 << K):
    cnt = bin(mask).count('1')
    if cnt > P:
        continue
    current = compute_paths(mask, friends, H, W)
    if current > max_count or (current == max_count and mask < best_mask):
        max_count = current
        best_mask = mask

if max_count == 0:
    print(0)
else:
    print(max_count % MOD)
    selected = []
    for i in range(K):
        if best_mask & (1 << i):
            selected.append(friends[i][2])
    for name in selected:
        print(name)
0