Overview

This problem asks us to rearrange the presentation order of employees under given constraints to maximize the total score \(\sum_{i=1}^{N} A_i \times P_i\).

Analysis

First, without any constraints, to maximize the total score, the optimal strategy is to arrange employees so that “those with higher presentation ability \(A_i\) present earlier (smaller rank \(P_i\)).” This is intuitively easy to understand — for example, if \(A = [3, 1, 2]\), setting the presentation order to \([3, 1, 2]\) → ranks \([1, 2, 3]\) maximizes the score.

However, in this problem, there are several constraints of the form “employee \(U_k\) must present before employee \(V_k\).” Such relationships can be represented as a directed graph and are related to the concept of topological sorting. We need to find an optimal permutation that satisfies all constraints.

A straightforward approach is to try all permutations. Since \(N\) is at most 8, the total number of permutations is at most \(8! = 40320\), which can be processed sufficiently fast. Therefore, a brute-force approach is both practical and safe.

The strategy is: 1. Generate all permutations. 2. For each permutation, check whether all constraints are satisfied. 3. If satisfied, compute the score and update the maximum value.

This allows us to obtain the correct answer.

Algorithm

1. Read the input and store the constraints in a list (converting to 0-indexed).
2. Use Python’s itertools.permutations to generate all possible presentation orders (permutations) of employees.
3. For each permutation, do the following:
   • For every condition \((u, v)\) in the constraint list, check whether \(u\) appears before \(v\) in the permutation.
   • If any violation is found, the permutation is invalid.
   • If all constraints are satisfied, compute the score \(\sum_{i=0}^{N-1} A[i] \times (\text{rank}_i + 1)\).
   • Update the maximum score.
4. Output the final maximum score.

Complexity

• Time complexity: \(O(N! \times M)\)
  • There are \(N!\) permutations, and for each one we check up to \(M\) constraints.
• Space complexity: \(O(N + M)\)
  • For the input array and the constraint list.

Implementation Notes

• Employee numbers are 1-indexed in the input, but converting them to 0-indexed internally makes list index operations easier.

• perm.index(i) gives the position (0-indexed) of employee \(i\) in the permutation, so adding 1 gives the rank.

• Permutations that violate constraints can be pruned early to avoid unnecessary computation (branch pruning).

  Source Code

from itertools import permutations

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    constraints = []
    for i in range(M):
        u = int(data[2+N + 2*i]) - 1  # 0-indexed
        v = int(data[2+N + 2*i + 1]) - 1
        constraints.append((u, v))
    
    max_score = -1
    
    for perm in permutations(range(N)):
        valid = True
        for u, v in constraints:
            if perm.index(u) >= perm.index(v):
                valid = False
                break
        if valid:
            score = sum(A[i] * (perm.index(i) + 1) for i in range(N))
            if score > max_score:
                max_score = score
                
    print(max_score)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.