結果

問題 No.2869 yuusaan's Knapsacks
コンテスト
ユーザー LyricalMaestro
提出日時 2025-11-02 20:15:18
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,524 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 717,776 KB
最終ジャッジ日時 2025-11-02 20:15:26
合計ジャッジ時間 7,411 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://yukicoder.me/problems/no/2869

def main():
    N, M = map(int, input().split())
    E = list(map(int, input().split()))
    vw = []
    for _ in range(M):
        v, w = map(int, input().split())
        vw.append((v ,w))

    # Eを耐久力がでかい順番にソート
    e_array = [(i, E[i]) for i in range(N)]
    e_array.sort(key=lambda x: x[1], reverse=True)

    start_index_map = [0] * (2 ** M)
    value_map = [0] * (2 ** M)
    weight_map = [0] * (2 ** M)
    for bit in range(2 ** M):
        start_index = -1
        v0 = 0
        w0 = 0
        for i in range(M):
            if (1 << i) & bit > 0:
                if start_index == -1:
                    start_index = i
                v, w = vw[i]
                v0 += v
                w0 += w
                
        start_index_map[bit] = start_index
        value_map[bit] = v0
        weight_map[bit] = w0

    # 分割方法の抽出
    def dfs(bit, top_index, array, array_set):
        bit1 = bit - (1 << top_index)
        bit0 = bit1
        while bit0 > 0:
            b = bit - bit0
            array.append(b)
            if len(array) <= (N + 1):
                x = start_index_map[bit0]
                dfs(bit0, x, array, array_set)
            array.pop()

            bit0 = (bit0 - 1) & bit1

        array.append(bit - bit0)
        if len(array) <= (N + 1):
            tpl = tuple(array)
            array_set.add(tpl)
        array.pop()

    array_set = set()
    dfs(2 ** M - 1, 0, [], array_set)

    max_answer = 0
    max_split = []
    for split_bits in array_set:
        array = []
        for bit in split_bits:
            array.append((weight_map[bit], bit))
        array.sort(reverse=True, key=lambda x:x[0])


        # 全て使うケース
        e_index = 0
        a_index = 0
        ans_array = []
        total_value = 0
        while e_index < N and a_index < len(array):
            w, bit = array[a_index]
            if w <= e_array[e_index][1]:
                a_index += 1
                ans_array.append((bit, e_array[e_index][0]))
                total_value += value_map[bit]
            e_index += 1
        
        if a_index == len(array):
            if max_answer < total_value:
                max_answer = total_value
                max_split = ans_array
        
        # 一部だけ使わないケース


        for j in range(len(array)):
            e_index = 0
            a_index = 0 if j != 0 else 1
            ans_array = []
            total_value = 0
            while e_index < N and a_index < len(array):
                w, bit = array[a_index]
                if w <= e_array[e_index][1]:
                    a_index += 1
                    if a_index == j:
                        a_index += 1

                    ans_array.append((bit, e_array[e_index][0]))
                    total_value += value_map[bit]
                e_index += 1
            
            if a_index == len(array):
                if max_answer < total_value:
                    max_answer = total_value
                    max_split = ans_array

    backets = [[] for _ in range(N)]
    for bit, e_index in max_split:
        for i in range(M):
            if (1 << i) & bit > 0:
                backets[e_index].append(i + 1)
    
    print(max_answer)
    for e_index in range(N):
        cnt = len(backets[e_index])
        if cnt == 0:
            print(cnt)
        else:
            print(cnt, " ".join(map(str, backets[e_index])))
 

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