Overview

This problem is a variant of the knapsack problem where we maximize the profit of exhibits within a capacity \(W\), while considering the delivery cost (the square of the number of selected venues, \(c^2\)).

The key observation is that the total number of venues \(K\) is very small (\(K \le 8\)). By exhaustively searching “which venues’ exhibits to select” using depth-first search (DFS) while simultaneously updating the knapsack DP (dynamic programming), we can efficiently find the optimal solution.

Analysis

1. Why can’t a simple knapsack DP solve this?

In a standard knapsack DP, we only manage the weight and profit of each individually selected exhibit. However, in this problem, the delivery cost of \(c^2\) is subtracted based on the “number of distinct venue types \(c\)” among the selected exhibits. Selecting multiple exhibits from the same venue doesn’t increase the cost, but selecting even one exhibit from a new venue causes the cost to jump significantly. Therefore, we need to incorporate “which venues’ exhibits have already been selected” into the DP state.

2. Leveraging the constraint \(K \le 8\)

The number of venues \(K\) is at most \(8\), which is very small. For each venue, there are only \(2\) choices: “select at least one exhibit from that venue (= use the venue)” or “select none (= don’t use the venue)”. The total number of combinations across all venues is at most \(2^K = 2^8 = 256\).

Therefore, if we decide in advance which venues to use, for each such decision (at most 256 patterns), we can solve a standard knapsack DP using only the exhibits belonging to the selected venues.

3. Efficient DP updates via DFS

If we solve the DP from scratch for each of the 256 patterns, there would be many redundant computations. Instead, we use depth-first search (DFS), branching on whether to “select” or “not select” each venue starting from venue \(1\), while incrementally updating the DP table.

• When venue \(i\) is “not selected”: The DP table is not updated, and we proceed directly to exploring the next venue.
• When venue \(i\) is “selected”: We copy the current DP table, apply transitions (updates) using the exhibits belonging to venue \(i\), and then proceed to exploring the next venue.

This allows us to reuse DP tables computed during the search, significantly reducing the computation.

---

Algorithm

1. Preprocessing

• Group exhibits by venue.
• To improve the effectiveness of pruning (early termination of search), sort venues in decreasing order of the number of exhibits they contain.
• Precompute the total profit sum of all exhibits remaining from each venue onward (prefix sum rem_val). This is used for pruning decisions.

2. DFS (Depth-First Search) Design

Define the DFS function as dfs(depth, current_dp, selected_count). - depth: The index of the venue currently being considered (\(0 \le \text{depth} \le K\)) - current_dp: An array (of size \(W+1\)) where current_dp[w] represents the maximum profit when the total weight is at most \(w\) - selected_count: The number of venues decided to be “selected” so far (\(= c\))

Search Steps:

1. Update the maximum value: The maximum profit in the current DP table is current_dp[W]. Update the overall maximum value ans with this value minus the delivery cost selected_count\(^2\).
2. Pruning: If “the current maximum profit current_dp[W]” plus “the total profit of all exhibits in the remaining venues rem_val[depth]” minus the current delivery cost is less than or equal to the current best ans, then there is no prospect of improving the maximum value by continuing the search, so we terminate (return).
3. Base case: If depth == K (all venues have been considered), terminate the search.
4. Transitions (branching):
   • Option 1 (don’t select): Select no exhibits from venue depth and proceed to the next venue. dfs(depth + 1, current_dp, selected_count)
   • Option 2 (select): Select some exhibits from venue depth, update the DP table, and proceed. Create next_dp as a copy of current_dp, and for each exhibit \((w_i, v_i)\) belonging to venue depth, perform the following 0-1 knapsack DP transition: $\(\text{next\_dp}[w] = \max(\text{next\_dp}[w], \text{next\_dp}[w - w_i] + v_i) \quad (w_i \le w \le W)\)$ After the update, call dfs(depth + 1, next_dp, selected_count + 1).

---

Complexity

Time Complexity: \(O(2^K \cdot N \cdot W)\) (worst case)

• The number of DFS branches is at most \(2^K\).
• At each branch, for the number of exhibits \(N_{\text{venue}}\) belonging to that venue, we update a DP table of size \(W\), so the transition cost per step is \(O(N_{\text{venue}} \cdot W)\).
• Overall, the worst-case time complexity is \(O(2^K \cdot N \cdot W)\), but due to powerful pruning (using rem_val) and the venue sorting strategy, the number of states actually explored is far fewer than \(2^K\). The execution time is very fast, ranging from a few milliseconds to tens of milliseconds.

Space Complexity: \(O(K \cdot W + N)\)

• The maximum recursion depth of the DFS is \(K\).
• The DP table maintained at each depth has size \(W + 1\).
• Therefore, the space complexity is \(O(K \cdot W + N)\), which is well within the memory limit.

---

Implementation Notes

• Update order for 0-1 knapsack DP: Since each exhibit can only be selected once, when updating the DP table, the weight \(w\) must be iterated in reverse order (from W down to w_i). This prevents the same exhibit from being selected multiple times.

• Venue sorting order: By processing venues with more exhibits first, we can establish a large profit (ans) early in the search. This makes the pruning condition current_dp[W] + rem_val[depth] - selected_count^2 <= ans more likely to hold, dramatically reducing unnecessary exploration.

  Source Code

import sys

# 再帰上限の変更（K <= 8 なので実際には不要だが念のため）
sys.setrecursionlimit(2000)


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    W = int(data[2])

    items_by_venue = [[] for _ in range(K + 1)]
    idx = 3
    for _ in range(N):
        w = int(data[idx])
        v = int(data[idx + 1])
        d = int(data[idx + 2])
        items_by_venue[d].append((w, v))
        idx += 3

    venues = [items_by_venue[i] for i in range(1, K + 1)]
    # 展示品数が多い会場から順に処理することで、DPの遷移回数を最小化する
    venues.sort(key=len, reverse=True)

    # 各深さ以降の会場に含まれる展示品の利益の総和（枝刈り用）
    rem_val = [0] * (K + 1)
    for i in range(K - 1, -1, -1):
        rem_val[i] = rem_val[i + 1] + sum(v for w, v in venues[i])

    ans = 0

    def dfs(depth, current_dp, selected_count):
        nonlocal ans

        # 現在のDPでの最大値を評価
        # current_dp は単調非減少なので、最大値は常に current_dp[W] となる
        val = current_dp[W] - selected_count * selected_count
        if val > ans:
            ans = val

        if depth == K:
            return

        # 枝刈り：残りの展示品をすべて選んでも暫定の最大値を超えられない場合は探索を打ち切る
        if current_dp[W] + rem_val[depth] - selected_count * selected_count <= ans:
            return

        # 選択肢1: 会場 depth を選ばない
        dfs(depth + 1, current_dp, selected_count)

        # 選択肢2: 会場 depth を選ぶ
        next_dp = current_dp[:]
        for w_i, v_i in venues[depth]:
            for w in range(W, w_i - 1, -1):
                if next_dp[w - w_i] + v_i > next_dp[w]:
                    next_dp[w] = next_dp[w - w_i] + v_i
        dfs(depth + 1, next_dp, selected_count + 1)

    init_dp = [0] * (W + 1)
    dfs(0, init_dp, 0)

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.