Overview

This problem asks us to determine a permutation for arranging \(N\) paintings at \(N\) positions, maximizing the total sum of products of the differences in color tone values between adjacent paintings and the weights of the partition walls. We leverage the constraint \(N \leq 16\) and solve it using bitmask DP.

Analysis

Naive Approach

Trying all permutations yields \(N!\) arrangements. When \(N = 16\), this is \(16! \approx 2 \times 10^{13}\), which is far too large to handle in time.

Key Insight

Looking carefully at the evaluation formula:

\[\sum_{i=1}^{N-1} |P_{Q_i} - P_{Q_{i+1}}| \times W_i\]

This can be thought of as a process of placing paintings one by one from left to right. When placing a painting at position \(k\) (0-indexed), the newly added evaluation value is determined solely by “the difference in color tone values with the painting placed at position \(k-1\) × \(W_{k-1}\)”.

In other words, as long as we know which paintings have already been used (as a set) and which painting was placed last, we can compute the value added in the next step. This is a classic structure for bitmask DP.

Algorithm

We use bitmask DP (Traveling Salesman Problem type).

State Definition

• \(dp[\text{mask}][j]\): The maximum evaluation value when the set of used paintings is \(\text{mask}\) (represented as bits) and the last placed painting is \(j\).

Initial State

The state where only painting \(j\) is placed at position \(0\):

\[dp[1 \ll j][j] = 0 \quad (0 \leq j < N)\]

Since there is no adjacent comparison yet, the evaluation value is \(0\).

Transition

Let \(bc\) be the number of set bits in \(\text{mask}\) (= the number of paintings already placed). The next painting will be placed at position \(bc\) (0-indexed). The wall weight between position \(bc-1\) and position \(bc\) is \(W[bc-1]\).

For an unused painting \(k\) (bit \(k\) of \(\text{mask}\) is \(0\)), placing it at position \(bc\):

\[dp[\text{mask} | (1 \ll k)][k] = \max\left(dp[\text{mask} | (1 \ll k)][k],\; dp[\text{mask}][j] + |P_j - P_k| \times W[bc-1]\right)\]

Answer

The maximum value when all paintings have been placed, i.e., when \(\text{mask} = 2^N - 1\):

\[\max_{j=0}^{N-1} dp[2^N - 1][j]\]

Concrete Example (N=3, P=[1,3,5], W=[2,4])

• Place one painting at position 0 (evaluation value 0)
• Place the next painting at position 1: compute the difference using wall weight \(W[0]=2\)
• Place the last painting at position 2: compute the difference using wall weight \(W[1]=4\)
• For example, with arrangement \((1,5,3)\): \(|1-5| \times 2 + |5-3| \times 4 = 8 + 8 = 16\)

Complexity

• Time complexity: \(O(2^N \times N^2)\) — for each state \((\text{mask}, j)\), enumerate unused paintings \(k\)
• Space complexity: \(O(2^N \times N)\) — size of the DP table

When \(N = 16\), this is approximately \(2^{16} \times 16^2 = 65536 \times 256 \approx 1.7 \times 10^7\), which is well within time limits.

Implementation Notes

• Enumerating unused paintings with bit operations: By setting remaining = full ^ mask and using the bits & -bits technique to extract the lowest set bit, we efficiently enumerate only the unused paintings.

• Determining current position with popcount: We count the number of placed paintings using bin(mask).count('1') and determine the next wall weight \(W[bc-1]\) to use.

• Managing initial values: The DP table is initialized with \(-1\) (unreached), and transitions from unreached states are skipped.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    P = [int(input_data[idx + i]) for i in range(N)]; idx += N
    W = [int(input_data[idx + i]) for i in range(N - 1)]; idx += N - 1

    if N == 1:
        print(0)
        return

    # Bitmask DP
    # dp[mask][j] = maximum evaluation value when we have placed paintings corresponding to
    # bits in mask, and the last painting placed (at position |mask|-1) is painting j.
    # |mask| tells us how many paintings have been placed so far.

    INF = -1
    full = (1 << N) - 1

    # Initialize dp as dict or array
    # Since N <= 16, mask can be up to 2^16 = 65536, and j up to 15
    # Total states: 65536 * 16 = ~1M, manageable

    dp = [[INF] * N for _ in range(1 << N)]

    # Base case: place one painting at position 0
    for j in range(N):
        dp[1 << j][j] = 0

    for mask in range(1, 1 << N):
        bc = bin(mask).count('1')
        if bc >= N:
            continue
        # Position of next painting to place is bc (0-indexed)
        # The wall between position bc-1 and bc has weight W[bc-1]
        w = W[bc - 1]  # bc >= 1 since we need at least 1 painting placed
        for j in range(N):
            if dp[mask][j] == INF:
                continue
            if not (mask & (1 << j)):
                continue
            val = dp[mask][j]
            pj = P[j]
            # Try placing painting k at position bc
            remaining = full ^ mask
            bits = remaining
            while bits:
                k = (bits & -bits).bit_length() - 1
                new_mask = mask | (1 << k)
                new_val = val + abs(pj - P[k]) * w
                if new_val > dp[new_mask][k]:
                    dp[new_mask][k] = new_val
                bits &= bits - 1

    print(max(dp[full]))

solve()

---

This editorial was generated by claude4.6opus-thinking.