結果

問題 No.2370 He ate many cakes
ユーザー lam6er
提出日時 2025-03-20 21:15:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 914 ms / 2,000 ms
コード長 1,607 bytes
コンパイル時間 350 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 136,612 KB
最終ジャッジ日時 2025-03-20 21:16:22
合計ジャッジ時間 7,273 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N
    
    mid = N // 2
    left = A[:mid]
    right = A[mid:]
    
    def get_subset_sums(arr):
        sums = [0]
        for num in arr:
            new_sums = [s + num for s in sums]
            sums += new_sums
        return sums
    
    left_subs = get_subset_sums(left)
    right_subs = get_subset_sums(right)
    
    left_subs.sort()
    right_subs.sort()
    
    max_i = len(left_subs) - 1
    max_j = len(right_subs) - 1
    
    heap = []
    visited = set()
    initial_sum = left_subs[max_i] + right_subs[max_j]
    heapq.heappush(heap, (-initial_sum, max_i, max_j))
    visited.add((max_i, max_j))
    
    result = 0
    for _ in range(K):
        current = heapq.heappop(heap)
        result = -current[0]
        i, j = current[1], current[2]
        
        # Check and push (i-1, j)
        if i > 0:
            new_i = i - 1
            if (new_i, j) not in visited:
                new_sum = left_subs[new_i] + right_subs[j]
                heapq.heappush(heap, (-new_sum, new_i, j))
                visited.add((new_i, j))
        # Check and push (i, j-1)
        if j > 0:
            new_j = j - 1
            if (i, new_j) not in visited:
                new_sum = left_subs[i] + right_subs[new_j]
                heapq.heappush(heap, (-new_sum, i, new_j))
                visited.add((i, new_j))
    
    print(result)

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