#1059607 (PyPy3) No.2869 yuusaan's Knapsacks

• 問題: No.2869 yuusaan's Knapsacks
• ユーザー: lam6er
• 提出日時: 2025-03-26 15:54:17
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 677 ms / 4,500 ms
• コード長: 3,822 bytes
• コンパイル時間: 346 ms
• コンパイル使用メモリ: 82,376 KB
• 実行使用メモリ: 90,548 KB
• 最終ジャッジ日時: 2025-03-26 15:55:14
• 合計ジャッジ時間: 8,887 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 27

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
import sys
from itertools import combinations
def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    e = list(map(int, input[ptr:ptr+N]))
    ptr += N
    items = []
    for j in range(M):
        v = int(input[ptr])
        w = int(input[ptr+1])
        ptr += 2
        items.append((v, w, j+1))  # j+1 is original index (1-based)
    # Generate all possible subsets, sorted by total value descending
    subsets = []
    for mask in range(1 << M):
        total_v = 0
        total_w = 0
        for j in range(M):
            if (mask >> j) & 1:
                total_v += items[j][0]
                total_w += items[j][1]
        subsets.append((mask, total_v, total_w))
    # Sort subsets by total_v descending, then mask ascending (for tie)
    subsets.sort(key=lambda x: (-x[1], x[0]))
    sum_e = sum(e)
    max_e = max(e) if e else 0
    # Precompute for each subset the items included
    for mask, total_v, total_w in subsets:
        if total_v == 0:
            continue
        if total_w > sum_e:
            continue
        # Check if all items in subset have weight <= max_e
        valid = True
        items_in_subset = []
        for j in range(M):
            if (mask >> j) & 1:
                if items[j][1] > max_e:
                    valid = False
                    break
                items_in_subset.append(items[j])
        if not valid:
            continue
        # Sort items in subset by weight descending
        items_sorted = sorted(items_in_subset, key=lambda x: (-x[1], x[2]))
        # Compute suffix sums
        suffix_weights = [0] * (len(items_sorted) + 1)
        for i in range(len(items_sorted)-1, -1, -1):
            suffix_weights[i] = suffix_weights[i+1] + items_sorted[i][1]
        # Prepare initial capacities (original order of knapsacks)
        caps = e.copy()
        # Prepare assignment: list of lists, one per knapsack
        assignment = [[] for _ in range(N)]
        # Backtracking function
        def backtrack(index, caps, assignment, suffix_weights):
            if index == len(items_sorted):
                return True, assignment
            item = items_sorted[index]
            sum_remaining = suffix_weights[index]
            sum_caps = sum(caps)
            if sum_remaining > sum_caps:
                return False, None
            max_w = item[1]
            max_cap = max(caps)
            if max_w > max_cap:
                return False, None
            # Get sorted list of knapsacks by remaining capacity descending, then index ascending
            sorted_caps = sorted([(cap, i) for i, cap in enumerate(caps)], key=lambda x: (-x[0], x[1]))
            for cap, i in sorted_caps:
                if cap >= item[1]:
                    new_caps = caps.copy()
                    new_assignment = [row.copy() for row in assignment]
                    new_caps[i] -= item[1]
                    new_assignment[i].append(item[2])  # store original item index
                    success, result_assignment = backtrack(index + 1, new_caps, new_assignment, suffix_weights)
                    if success:
                        return True, result_assignment
            return False, None
        # Start backtracking
        success, result_assignment = backtrack(0, caps, assignment, suffix_weights)
        if success:
            print(total_v)
            for knapsack in result_assignment:
                print(len(knapsack), end=' ')
                if len(knapsack) > 0:
                    print(' '.join(map(str, sorted(knapsack))), end='')
                print()
            return
    # If no subset found (unlikely)
    print(0)
    for _ in range(N):
        print(0)
    return
if __name__ == '__main__':
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX