結果

問題 No.733 分身並列コーディング
ユーザー gew1fw
提出日時 2025-06-12 16:13:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 468 ms / 1,500 ms
コード長 1,729 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 82,788 KB
最終ジャッジ日時 2025-06-12 16:13:20
合計ジャッジ時間 6,076 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    T = int(sys.stdin.readline())
    N = int(sys.stdin.readline())
    t = [int(sys.stdin.readline()) for _ in range(N)]
    t.sort(reverse=True)  # Sort in descending order for efficiency

    # Precompute the sum of all possible subsets
    precomputed_sums = [0] * (1 << N)
    for mask in range(1 << N):
        s = 0
        for i in range(N):
            if mask & (1 << i):
                s += t[i]
        precomputed_sums[mask] = s

    def can_assign(groups_left, mask, memo):
        if mask == 0:
            return True
        if groups_left == 0:
            return False
        key = (groups_left, mask)
        if key in memo:
            return memo[key]
        
        # Find the first unassigned problem
        first = 0
        for i in range(N):
            if (mask >> i) & 1:
                first = i
                break
        
        s = mask ^ (1 << first)
        subset = s
        success = False
        while True:
            current_subset = subset | (1 << first)
            total = precomputed_sums[current_subset]
            if total <= T:
                new_mask = mask ^ current_subset
                if can_assign(groups_left - 1, new_mask, memo):
                    success = True
                    break
            if subset == 0:
                break
            subset = (subset - 1) & s
        
        memo[key] = success
        return success

    for k in range(1, N + 1):
        memo = {}
        full_mask = (1 << N) - 1
        if can_assign(k, full_mask, memo):
            print(k)
            return
    
    print(N)  # This line is theoretically unreachable

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