結果

問題 No.733 分身並列コーディング
ユーザー lam6er
提出日時 2025-04-15 21:08:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,117 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 77,172 KB
最終ジャッジ日時 2025-04-15 21:13:52
合計ジャッジ時間 3,985 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    T = int(sys.stdin.readline())
    N = int(sys.stdin.readline())
    t = [int(sys.stdin.readline()) for _ in range(N)]
    
    sum_t = [0] * (1 << N)
    for mask in range(1 << N):
        total = 0
        for i in range(N):
            if mask & (1 << i):
                total += t[i]
        sum_t[mask] = total
    
    full_mask = (1 << N) - 1
    sum_total = sum(t)
    
    @lru_cache(maxsize=None)
    def can_divide(mask, groups_left):
        if groups_left == 0:
            return mask == 0
        s = mask
        while True:
            if s != 0 and sum_t[s] <= T:
                new_mask = mask ^ s
                if can_divide(new_mask, groups_left - 1):
                    return True
            if s == 0:
                break
            s = (s - 1) & mask
        return False
    
    for k in range(1, N + 1):
        if sum_total > k * T:
            continue
        can_divide.cache_clear()
        if can_divide(full_mask, k):
            print(k)
            return
    
    print(N)

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