Overview

This problem asks us to optimize the arrangement (permutation) of \(N\) paintings to maximize the total sum of products between the difference in tonal values of adjacent paintings and the weight of the partition wall at that position. Since the constraint is small with \(N \le 16\), we can solve this using bit DP (dynamic programming), similar to the approach used for the Traveling Salesman Problem (TSP).

Analysis

First, let’s consider a naive approach of exhaustively searching all possible arrangements (enumerating all permutations). The total number of arrangements is \(N!\), but when \(N = 16\), \(16! \approx 2.09 \times 10^{13}\), which is far too large to compute within the time limit (it would result in TLE).

Here, let’s focus on how the evaluation value is calculated. When placing paintings from left to right, the newly added evaluation value is determined solely by the difference between “the previously placed painting” and “the newly placed painting”. In other words, when deciding which painting to place next, we don’t need to remember the entire order in which paintings were placed so far. The following two pieces of information are sufficient: 1. Which paintings have been used so far (the set of used paintings) 2. Which painting was placed last

By consolidating states in this way, we can dramatically reduce the number of patterns to examine. This is exactly the bit DP technique commonly used for solving the “Traveling Salesman Problem.”

Algorithm

We perform bit DP where the set of paintings is represented as a bitmask \(S\). (Example: if paintings \(0\) and \(2\) have been used, then \(S = 101_{(2)} = 5\))

1. DP Table Definition Define \(dp[S][u]\) as “the maximum evaluation value when the set of already placed paintings is \(S\) and the last placed (rightmost) painting is \(u\).” (Initialize impossible states with \(-1\).)

2. Initial State Start by selecting and placing just one painting. For all \(i\) \((0 \le i \le N-1)\), set \(dp[1 \ll i][i] = 0\). (Since no wall has been crossed yet, the evaluation value is \(0\).)

3. Transition Let \(S\) be the set of already placed paintings and \(u\) be the last placed painting. Consider placing a painting \(v\) (\(v \notin S\)) that has not been placed yet.

At this point, if the number of paintings in \(S\) is \(k\), then the next partition wall to cross is the \(k\)-th wall from the left, so its weight is \(W_k\) (or \(W_{k-1}\) in 0-indexed). Therefore, the new evaluation value is the current evaluation value plus \(|P_u - P_v| \times W_{k-1}\).

The transition formula is as follows: $\(dp[S \cup \{v\}][v] = \max(dp[S \cup \{v\}][v], dp[S][u] + |P_u - P_v| \times W_{k-1})\)$

1. Answer In the state where all paintings have been placed (\(S = (1 \ll N) - 1\)), the answer is the maximum evaluation value regardless of which painting \(u\) was placed last. $\(\max_{0 \le u \le N-1} dp[(1 \ll N) - 1][u]\)$

Complexity

• Time complexity: \(O(2^N N^2)\) There are \(2^N \times N\) states, and for each state we try up to \(N\) possible paintings \(v\) to place next. When \(N=16\), this results in approximately \(2^{16} \times 16^2 \approx 1.6 \times 10^7\) loop iterations, which is well within the time limit.
• Space complexity: \(O(2^N N)\) This is for maintaining the DP table as a \(2^N \times N\) array.

Implementation Notes

In scripting languages such as Python, careful attention to execution speed (constant factors) is necessary. The solution code achieves speedup through the following optimizations: - Precomputation: The tonal value differences \(|P_u - P_v|\) between paintings are precomputed and stored in a 2D array diff. - Element classification for each set: For each state \(S\), the “included elements (in_s),” “excluded elements (out_s),” and “element count (popcount)” are precomputed and stored in lists. This eliminates the need for bitwise checks inside the main DP loop, allowing us to directly iterate over only the necessary elements, leading to significant speedup.

Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    n = int(data[0])
    p = [int(x) for x in data[1:n+1]]
    w = [int(x) for x in data[n+1:2*n]]
    
    diff = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            diff[i][j] = abs(p[i] - p[j])

    dp = [[-1] * n for _ in range(1 << n)]
    for i in range(n):
        dp[1 << i][i] = 0
        
    popcount = [0] * (1 << n)
    in_s = [[] for _ in range(1 << n)]
    out_s = [[] for _ in range(1 << n)]
    for s in range(1 << n):
        popcount[s] = popcount[s >> 1] + (s & 1)
        for i in range(n):
            if s & (1 << i):
                in_s[s].append(i)
            else:
                out_s[s].append(i)
                
    for s in range(1, (1 << n) - 1):
        k = popcount[s]
        weight = w[k - 1]
        
        dp_s = dp[s]
        for u in in_s[s]:
            curr = dp_s[u]
            if curr == -1:
                continue
            
            diff_u = diff[u]
            for v in out_s[s]:
                val = curr + diff_u[v] * weight
                nxt_s = s | (1 << v)
                if val > dp[nxt_s][v]:
                    dp[nxt_s][v] = val
                        
    print(max(dp[(1 << n) - 1]))

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.1-pro-thinking.