結果
問題 | No.733 分身並列コーディング |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()