Overview

We determine a permutation that arranges paintings from left to right, and maximize the total sum of the color tone difference \(|P_a-P_b|\) between adjacent paintings multiplied by the wall weight \(W_i\). Since \(N\le 16\), we use dynamic programming with sets (bitmasks) to find the maximum value by processing “from left to right.”

Analysis

Key Observation

The evaluation value is [ \sum{i=1}^{N-1} |P{Qi}-P{Q_{i+1}}|\times W_i ] and each term is determined solely by “the two paintings placed at positions \(i\) and \(i+1\)” and “the wall weight \(W_i\) between them.”

In other words, when placing paintings from left to right: - We have already placed \(k\) paintings (positions \(1\sim k\) are determined) - We decide which painting to place as the \((k+1)\)-th

The increase in evaluation is the difference between “the last painting” and “the next painting” multiplied by \(W_k\) (since the boundary is between positions \(k\) and \(k+1\), the weight is \(W_k\)).

Why the Naive Approach Fails

Trying all permutations gives \(N!\) possibilities, and for \(N=16\): [ 16!\approx 2.1\times 10^{13} ] which is far too many for brute force.

How to Solve It

By managing “which paintings have been used” as a set and additionally keeping track of “the last painting placed” as part of the state, we can: - Among all paths that reach the same set and same last painting, keep only the one with the maximum evaluation value

This compresses the search space (a classic bitDP / Traveling Salesman-type DP).

Algorithm

State Definition

Let the bitmask \(\text{mask}\) represent “the set of paintings already placed” (the \(i\)-th bit is 1 if painting \(i\) has been used).

[ dp[\text{mask}][\text{last}] ] is defined as follows:

• The paintings in \(\text{mask}\) have been arranged from the left, with \(k=\mathrm{popcount}(\text{mask})\) paintings placed
• The rightmost painting (at position \(k\)) is last
• The maximum evaluation value achieved so far

Initialization — when only one painting is placed, the evaluation is 0: [ dp[1\ll i][i]=0 ]

Transition

Let \(k=\mathrm{popcount}(\text{mask})\) be the size of \(\text{mask}\). The next painting is placed at position \(k+1\). The increase in evaluation comes from the boundary between positions \(k\) and \(k+1\), so the weight is \(W_k\) (in 1-indexed \(W_{k}\), or W[k-1] in a 0-indexed array).

For nxt being an unused painting: [

dp[\text{mask}\cup{nxt}][nxt]

\max\Big( dp[\text{mask}\cup{nxt}][nxt],\; dp[\text{mask}][last] + |P{last}-P{nxt}|\times W_k \Big) ]

In the code, since we are transitioning from a state with \(k\) paintings placed, we use weight = W[k-1] (due to 0-indexing).

Answer

For the full mask \(\text{full}=(1\ll N)-1\): [ \max_{last} dp[\text{full}][last] ] is the answer (we take the maximum over all possible last paintings).

Implementation Tips

• Since \(|P_i-P_j|\) is used frequently, precompute all values as dist[i][j].
• To enumerate unused paintings, extract the lowest set bit using r & -r for efficient iteration.

Complexity

• Time complexity: \(O(N^2 2^N)\)
  (The number of states is \(N2^N\), with up to \(N\) transitions from each state)
• Space complexity: \(O(N2^N)\)
  (DP table)

Implementation Notes

• Pay attention to the boundary weight correspondence: when transitioning from a state with \(k\) paintings placed, the weight used is “between positions \(k\) and \(k+1\),” which corresponds to W[k-1] in a 0-indexed array.

• Managing unreached states as None in dp and branching during max updates is a safe approach.

• In Python, mask.bit_count() is fast and works very well with bitDP for \(N\le16\).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    P = list(map(int, input().split()))
    W = list(map(int, input().split()))
    full = (1 << N) - 1

    dist = [[0] * N for _ in range(N)]
    for i in range(N):
        pi = P[i]
        for j in range(N):
            dist[i][j] = abs(pi - P[j])

    dp = [[None] * N for _ in range(1 << N)]
    for i in range(N):
        dp[1 << i][i] = 0

    for mask in range(1 << N):
        k = mask.bit_count()
        if k == 0 or k == N:
            continue
        weight = W[k - 1]
        rem = full ^ mask
        row = dp[mask]
        for last in range(N):
            val = row[last]
            if val is None:
                continue
            r = rem
            dlast = dist[last]
            while r:
                lsb = r & -r
                nxt = lsb.bit_length() - 1
                nmask = mask | lsb
                nv = val + dlast[nxt] * weight
                cur = dp[nmask][nxt]
                if cur is None or nv > cur:
                    dp[nmask][nxt] = nv
                r -= lsb

    ans = max(v for v in dp[full] if v is not None)
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.