Overview

This is a problem of maximizing \(\sum_{i=1}^{N} A_i P_i\) among all presentation orders (topological orderings) that satisfy the constraints (relationships where certain presentations must come before others). Since \(N \le 8\), we can efficiently perform an exhaustive search using DP with sets represented as bits (bit DP).

Analysis

• The presentation order \((P_1,\dots,P_N)\) is a problem of “lining up employees one by one.” However, if there is an edge \(U \to V\), then \(U\) must be placed before \(V\) (topological order of a DAG).
• The objective function is \(\sum A_i \times P_i\), where the score is determined by “which position each employee is placed at.”
  In other words, if we know “who has been placed so far (as a set),” the incremental score when choosing the next employee to place (\(A_v \times \text{next position}\)) is determined.
• Naively trying all permutations would be \(N!\) cases, and including constraint checks makes the implementation somewhat cumbersome. With \(N \le 8\), \(N!\) might seem feasible, but in competitive programming, “constrained order optimization” is typically handled with bit DP, which is easier to extend and safer.
• Therefore, we perform DP with the state being “the set of employees who have already finished their presentations.” The next employee we can place must have all their prerequisites (employees who must present before them) already included in the set.

Algorithm

1. Store prerequisites as bit sets

Number employees from \(0\) to \(N-1\), and for each constraint \(u \to v\) (\(u\) comes before \(v\)): - pred[v]: the “set of employees that must have presented before employee \(v\)” stored as bits.

Example: With \(N=4\) and constraints “1 before 3” and “2 before 3,” then (0-indexed) pred[2] has the bits for {0,1} set.

2. Bit DP

• State mask: the set of employees who have already presented (bit 1 means done)
• dp[mask]: the maximum total score achievable up to this state

Initial values: - dp[0] = 0 - All others are set to a sufficiently small value (negative infinity) to indicate unreachable states

Transition: - When at state mask, the next presentation position is
\(\text{pos} = (\text{number of people in mask}) + 1\)
In code: pos = mask.bit_count() + 1 - For each employee \(v\) who has not yet presented, the condition to place them next is
“all prerequisite employees of \(v\) are in mask”
Written with bit operations:
pred[v] & ~mask == 0 (no unmet prerequisites) - If placeable: - nmask = mask | (1<<v) - dp[nmask] = max(dp[nmask], dp[mask] + A[v] * pos)

The answer is dp[(1<<N)-1] (the state where all employees have presented).

Complexity

• Time complexity: \(O(N \cdot 2^N)\)
  (For each of the \(2^N\) states, we try up to \(N\) employees to place next)
• Space complexity: \(O(2^N)\)
  (DP array)

Implementation Notes

• Prerequisite checking can be done in one step by checking whether pred[v] & ~mask is 0. Since ~mask is the bitwise complement, it helps to think of it as representing the “set of employees who have not yet presented.”

• The initial values of dp should be set to a sufficiently small value (e.g., -10**30) to represent unreachable states, and max is taken during updates.

• The next presentation position is “number of people placed so far + 1,” so using mask.bit_count() makes it concise.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    pred = [0] * N
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        pred[v] |= 1 << u

    INF_NEG = -10**30
    dp = [INF_NEG] * (1 << N)
    dp[0] = 0

    for mask in range(1 << N):
        if dp[mask] == INF_NEG:
            continue
        pos = mask.bit_count() + 1
        for v in range(N):
            if (mask >> v) & 1:
                continue
            if pred[v] & ~mask:
                continue
            nmask = mask | (1 << v)
            val = dp[mask] + A[v] * pos
            if val > dp[nmask]:
                dp[nmask] = val

    print(dp[(1 << N) - 1])

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.