結果

問題 No.2178 Payable Magic Items
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:21:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,872 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 82,552 KB
実行使用メモリ 276,840 KB
最終ジャッジ日時 2025-03-20 20:24:12
合計ジャッジ時間 57,034 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import itertools

def main():
    input = sys.stdin.read().split()
    idx = 0
    N, K = int(input[idx]), int(input[idx+1])
    idx +=2

    points_input = []
    for _ in range(N):
        s = input[idx]
        digits = tuple(map(int, list(s)))
        points_input.append(digits)
        idx += 1

    # Generate all possible points (K-dimensional)
    all_points = list(itertools.product(range(5), repeat=K))
    code_to_idx = {p:i for i, p in enumerate(all_points)}
    total_points = len(all_points)

    # Initialize presence and cumsum
    presence = [0] * total_points
    for p in points_input:
        idx_p = code_to_idx[p]
        presence[idx_p] = 1

    cumsum = presence.copy()

    # Precompute code to index mapping for all points
    for d in range(K):
        # Sort all points in decreasing order of current dimension d
        sorted_points = sorted(all_points, key=lambda x: x[d], reverse=True)
        # Temporary array to hold new cumsum values for this dimension
        new_cumsum = [0] * total_points

        # For each point in sorted order (by dimension d)
        for p in sorted_points:
            code = code_to_idx[p]
            current_sum = cumsum[code]
            current_val = p[d]
            if current_val < 4:
                q = list(p)
                q[d] = current_val + 1
                q_tuple = tuple(q)
                q_code = code_to_idx[q_tuple]
                current_sum += new_cumsum[q_code]
            new_cumsum[code] = current_sum

        # Update cumsum after processing dimension d
        cumsum = new_cumsum

    # Now check each input point
    count = 0
    for p in points_input:
        code = code_to_idx[p]
        # The sum includes itself, so if sum is >=2, it's sellable
        if cumsum[code] >= 2:
            count += 1

    print(count)

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