Overview

This problem asks you to select some exhibits and load them onto a truck (capacity \(W\)), maximizing the value of “total expected profit of selected exhibits” minus “delivery cost (square of the number of distinct venues visited).”

By noting that the total number of venues \(K\) satisfies \(1 \le K \le 8\) (very small), we can efficiently solve this within the time limit by combining bitmask DP (subset DP) with \(0-1\) knapsack DP.

---

Analysis

1. Fixing the Choice of Venues

The delivery cost depends only on the “number of distinct venues \(c\)” among the selected exhibits. Suppose we fix in advance the set of venues \(S\) (\(S \subseteq \{1, 2, \dots, K\}\)) from which we will select exhibits.

In this case, the number of venues visited is fixed at \(c = |S|\), so the delivery cost is determined as \(c^2\). Therefore, the maximum profit given a fixed set \(S\) can be found by solving the following problem (a standard \(0-1\) knapsack problem):

“Using only exhibits from venues in set \(S\), find the maximum expected profit when the total weight does not exceed \(W\).”

By solving this knapsack problem for all possible sets \(S\) (there are \(2^K - 1\) non-empty sets), computing (maximum profit) - |S|^2 for each \(S\), and taking the overall maximum, we can obtain the answer.

2. Speeding Up Redundant Computations with DP

If we solve the knapsack DP from scratch for each of the \(2^K\) subsets, the computational cost becomes too large. Instead, we leverage the inclusion relationship between sets to reuse (transition from) previously computed DP tables.

Let dp[S][w] be the DP table for set \(S\) (the maximum profit using only exhibits from set \(S\) with weight at most \(w\)). Let \(prev\_S = S \setminus \{j\}\) be the set obtained by removing any single venue \(j \in S\) from \(S\). Then dp[S] can be constructed incrementally as follows:

1. Copy the result of dp[prev_S] into dp[S] (corresponding to not selecting any exhibits from venue \(j\)).
2. Update the dp[S] table using exhibits belonging to venue \(j\) (corresponding to selecting exhibits from venue \(j\)).

By transitioning set \(S\) as “an already computed subset \(prev\_S\)” with “exhibits from a new venue \(j\) added,” we eliminate redundant recomputation.

---

Algorithm

Step 1: Sorting Venues (Optimization)

To reduce computational cost, we sort venue indices in ascending order of their number of exhibits, so that venues with fewer exhibits are used as “transition sources for more sets \(S\).” (See “Complexity” and “Implementation Notes” for details.)

Step 2: Updating the DP Table

Define dp[S][w] as “the maximum profit with weight limit \(w\) when considering only exhibits belonging to the set of venues \(S\).”

1. Initialize the dp table with \(0\).
2. Loop \(S\) from \(1\) to \(2^K - 1\).
3. Let \(j\) be the rightmost set bit (lowest set bit) of \(S\).
4. Let \(prev\_S = S \setminus \{j\}\) (the set \(S\) with \(j\) removed).
5. Copy dp[prev_S] into dp[S].
6. For each exhibit \(i\) belonging to venue \(j\) (the actual venue number after sorting), update dp[S] as follows: $\(dp[S][w] = \max(dp[S][w], dp[S][w - w_i] + v_i) \quad (w = W, W-1, \dots, w_i)\)$

Step 3: Computing the Answer

For all sets \(S\) (\(0 \le S < 2^K\)), compute the following and find the maximum: $\(\text{maximum} = \max_{S} \left( dp[S][W] - |S|^2 \right)\)\( Here, \)|S|\( is the number of venues in set \)S$ (the number of set bits in the binary representation).

---

Complexity

Time Complexity

The number of sets \(S\) for which venue \(j\) (\(0 \le j < K\)) is chosen as the lowest set bit is \(2^{K - 1 - j}\). Let \(N_j\) be the number of exhibits belonging to venue \(j\). The overall complexity is:

\[O\left( \sum_{j=0}^{K-1} 2^{K - 1 - j} \cdot N_j \cdot W \right)\]

In the worst case, since the total number of exhibits is \(\sum N_j = N\), when each venue has approximately the same number of exhibits (\(N/K\)), the overall complexity is approximately \(O(2^K \cdot \frac{N}{K} \cdot W)\). Substituting the constraints of this problem (\(N \le 300, K \le 8, W \le 3000\)), the number of operations in the worst case is approximately \(2.8 \times 10^7\), which comfortably fits within the time limit.

Space Complexity

• \(O(2^K \cdot W)\)

The DP table size is \(2^K \times (W + 1)\). This is \(2^8 \times 3001 \approx 7.7 \times 10^5\) elements (approximately 6.1 MB with long long type), which is well within the memory limit.

---

Implementation Notes

• Fast retrieval of the lowest set bit: By using std::countr_zero introduced in C++20, the index \(j\) of the lowest set bit of set \(S\) can be obtained in constant time.

• Fast popcount: When computing the number of selected venues \(|S|\), using std::popcount from C++20 allows fast counting of the number of set bits.

• Optimization by sorting venues: The number of transitions (\(2^{K-1-j}\)) is larger for smaller index \(j\) (lower bits). Therefore, by placing venues with fewer exhibits \(N_j\) at lower indices (lower bit positions), the number of expensive knapsack DP transitions is dramatically reduced, significantly improving execution speed.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <bit>

using namespace std;

struct Item {
    int w;
    long long v;
};

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K, W;
    if (!(cin >> N >> K >> W)) return 0;

    vector<vector<Item>> items_by_venue(K);
    for (int i = 0; i < N; ++i) {
        int w, d;
        long long v;
        cin >> w >> v >> d;
        --d; // Convert to 0-indexed
        items_by_venue[d].push_back({w, v});
    }

    // Optimization: Sort venue indices by the number of items in ascending order.
    // This minimizes the overall computation because the transition cost
    // in the DP depends on the size of the set's least significant bit.
    vector<int> p(K);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int a, int b) {
        return items_by_venue[a].size() < items_by_venue[b].size();
    });

    // dp[S][w] stores the maximum profit using a subset of venues S with total weight <= w
    vector<vector<long long>> dp(1 << K, vector<long long>(W + 1, 0));

    for (int S = 1; S < (1 << K); ++S) {
        int j = std::countr_zero((unsigned int)S);
        int prev_S = S ^ (1 << j);
        
        // Copy the DP state from the subset without venue j
        dp[S] = dp[prev_S];
        
        // Update the DP state by incorporating items from venue j
        for (const auto& item : items_by_venue[p[j]]) {
            for (int w = W; w >= item.w; --w) {
                dp[S][w] = max(dp[S][w], dp[S][w - item.w] + item.v);
            }
        }
    }

    long long ans = 0;
    for (int S = 0; S < (1 << K); ++S) {
        int c = std::popcount((unsigned int)S);
        long long profit = dp[S][W];
        long long cost = (long long)c * c;
        ans = max(ans, profit - cost);
    }

    cout << ans << "\n";

    return 0;
}

---

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