Overview

This is a problem where we need to determine the presentation order of \(N\) employees while satisfying given precedence constraints. We must find the presentation order that maximizes the total score, defined as the sum of each employee’s “presentation skill \(\times\) presentation order,” and output that maximum value.

Analysis

The most important observation in this problem is that the constraint on the number of employees \(N\) is very small: \(1 \leq N \leq 8\).

The total number of ways to arrange \(N\) employees (permutations) is \(N!\) (\(N\) factorial). Even for the maximum \(N=8\), there are only \(8! = 40,320\) permutations. For each presentation order, we can: 1. Check whether all constraints are satisfied 2. If satisfied, compute the total score

Even performing this processing for all permutations, the total number of computations is at most on the order of hundreds of thousands. This is easily handled within the time limit by modern computers (including Python).

If \(N\) were much larger, we would need to consider approaches like dynamic programming, but since \(N \leq 8\) in this problem, a brute-force approach of “trying all possible presentation orders and finding the maximum score among those satisfying the conditions” (exhaustive permutation search) can reliably produce the correct answer.

Algorithm

1. Using Python’s standard library itertools.permutations, generate all permutations of employee numbers from \(0\) to \(N-1\). The \(i\)-th element of a permutation represents “the employee who presents \(i\)-th.”
2. From each generated permutation, create an array pos that records “what position each employee presents at.” For example, the presentation order of employee \(u\) can be retrieved as pos[u].
3. Check each of the \(M\) constraints \((U_k, V_k)\) one by one. If pos[U_k] > pos[V_k] (meaning \(U_k\) presents after \(V_k\)), this permutation does not satisfy the conditions, so we skip it.
4. If all constraints are satisfied, compute the total score \(\displaystyle\sum_{i=0}^{N-1} A_i \times (\text{pos}[i] + 1)\). (Since the presentation order in the problem statement is 1-indexed, we add \(1\) to pos[i].)
5. Update the maximum value with the computed score, and after trying all permutations, the final maximum value is the answer.

Complexity

• Time complexity: \(O(N! \times (N + M))\)
  • For all \(N!\) permutations, creating the presentation order array takes \(O(N)\), checking constraints takes \(O(M)\), and computing the score takes \(O(N)\). Even for the maximum case of \(N=8, M=28\), the total internal loop operations are on the order of a few million, which is sufficiently fast.
• Space complexity: \(O(N + M)\)
  • \(O(N)\) memory is used to store the presentation skills \(A\) and the presentation order pos, and \(O(M)\) memory is used to store the constraints.

Implementation Notes

• Converting to 0-indexed: The employee numbers and constraints given in the input range from \(1\) to \(N\), but handling them internally as \(0\) to \(N-1\) to match array indices makes the implementation cleaner. Subtract \(1\) from \(U_k, V_k\) at the input stage.

• Adjustment during score calculation: Internally, positions are managed from \(0\) to \(N-1\), but in the score definition, the presentation order \(P_i\) ranges from \(1\) to \(N\). Therefore, be careful not to forget to multiply by pos[i] + 1 when computing the score.

• Handling permutations: What permutations(range(N)) generates is “employee numbers arranged in order.” The key technique is to create a reverse-lookup array pos each time, which tells us “what position employee \(i\) is in,” making constraint checking and score calculation straightforward.

  Source Code

import sys
from itertools import permutations

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    M = int(data[1])
    
    A = [int(x) for x in data[2:2+N]]
    
    constraints = []
    idx = 2 + N
    for _ in range(M):
        u = int(data[idx]) - 1
        v = int(data[idx+1]) - 1
        constraints.append((u, v))
        idx += 2
        
    ans = -1
    for p in permutations(range(N)):
        pos = [0] * N
        for i, emp in enumerate(p):
            pos[emp] = i
            
        ok = True
        for u, v in constraints:
            if pos[u] > pos[v]:
                ok = False
                break
                
        if ok:
            score = sum(A[i] * (pos[i] + 1) for i in range(N))
            if score > ans:
                ans = score
                
    print(ans)

if __name__ == '__main__':
    main()

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