結果

問題 No.733 分身並列コーディング
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:40:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,801 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 82,756 KB
実行使用メモリ 188,788 KB
最終ジャッジ日時 2025-03-20 20:40:28
合計ジャッジ時間 3,293 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def solve():
    T_val = int(sys.stdin.readline())
    N = int(sys.stdin.readline())
    times = [int(sys.stdin.readline()) for _ in range(N)]
    times.sort(reverse=True)  # Sorting for efficient pruning

    full_mask = (1 << N) - 1

    for k in range(1, N + 1):
        dp = {}
        initial = tuple([0] * k)
        dp[0] = initial
        queue = deque([0])
        found = False

        while queue:
            mask = queue.popleft()
            current = list(dp[mask])

            # Find the first unset bit (next problem to assign)
            for i in range(N):
                if not (mask & (1 << i)):
                    ti = times[i]
                    # Try to add this problem to each possible group
                    for g in range(k):
                        if current[g] + ti > T_val:
                            continue
                        new_current = current.copy()
                        new_current[g] += ti
                        new_current_sorted = sorted(new_current)
                        new_mask = mask | (1 << i)

                        if new_mask == full_mask:
                            found = True
                            break

                        new_state = tuple(new_current_sorted)
                        if new_mask not in dp or new_state < dp[new_mask]:
                            dp[new_mask] = new_state
                            queue.append(new_mask)

                    if found:
                        break
                if found:
                    break
            if found:
                break
        if found:
            print(k)
            return

    print(N)  # Fallback, though constraints ensure it's not necessary

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