結果

問題 No.2178 Payable Magic Items
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:04:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,448 bytes
コンパイル時間 450 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 275,156 KB
最終ジャッジ日時 2025-04-16 16:12:08
合計ジャッジ時間 6,302 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 TLE * 1
other AC * 4 TLE * 4 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import product

def main():
    N, K = map(int, sys.stdin.readline().split())
    input_tuples = []
    for _ in range(N):
        s = sys.stdin.readline().strip()
        t = tuple(int(c) for c in s)
        input_tuples.append(t)
    input_set = set(input_tuples)
    
    # Initialize sum_dict with all possible tuples
    sum_dict = {}
    for t in product(*[range(5) for _ in range(K)]):
        sum_dict[t] = 1 if t in input_set else 0
    
    # Process each dimension to compute suffix sums
    for d in range(K):
        for current_d_val in range(4, -1, -1):
            # Generate all possible combinations for the other K-1 dimensions
            for other_dims in product(*[range(5) for _ in range(K-1)]):
                # Split other_dims into left and right parts around the current dimension d
                left = list(other_dims[:d])
                right = list(other_dims[d:])
                s_list = left + [current_d_val] + right
                s = tuple(s_list)
                if current_d_val < 4:
                    next_s_list = s_list.copy()
                    next_s_list[d] += 1
                    next_s = tuple(next_s_list)
                    sum_dict[s] += sum_dict[next_s]
    
    # Count the number of tuples that can be sold
    answer = 0
    for x in input_tuples:
        if sum_dict[x] >= 2:
            answer += 1
    print(answer)

if __name__ == "__main__":
    main()
0