結果

問題 No.733 分身並列コーディング
ユーザー lam6er
提出日時 2025-03-20 20:21:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 65 ms / 1,500 ms
コード長 1,303 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,740 KB
実行使用メモリ 76,272 KB
最終ジャッジ日時 2025-03-20 20:24:00
合計ジャッジ時間 3,287 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin

def main():
    T = int(stdin.readline())
    N = int(stdin.readline())
    tasks = [int(stdin.readline()) for _ in range(N)]
    tasks.sort(reverse=True)  # Sort in descending order
    sum_time = sum(tasks)
    
    # Determine lower bound for k
    if sum_time == 0:
        print(0)
        return
    lower_k = max((sum_time + T - 1) // T, 1)
    
    for k in range(lower_k, N + 1):
        buckets = [0] * k
        if backtrack(tasks, T, buckets, 0):
            print(k)
            return
    
    print(N)
    
def backtrack(tasks, T, buckets, index):
    if index == len(tasks):
        return True
    current = tasks[index]
    for i in range(len(buckets)):
        if buckets[i] + current > T:
            continue
        # Prune 1: Skip if previous bucket has the same sum to avoid duplicate
        if i > 0 and buckets[i] == buckets[i-1]:
            continue
        # Prune 2: Skip if current bucket is empty and there was a previous empty bucket
        if buckets[i] == 0 and any(buckets[j] == 0 for j in range(i)):
            continue
        # Proceed
        buckets[i] += current
        if backtrack(tasks, T, buckets, index + 1):
            return True
        buckets[i] -= current
    return False

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