Overview

In this problem, we are given \(N\) cities and \(M\) one-way roads (a directed graph). The goal is to choose a path of length \(K\) days to maximize the total score obtained.

The score obtained by staying in city \(i\) on day \(j\) is \((P_i \times j) \bmod Q\). Since the score changes depending on the day (the step count), we need an efficient search method.

Analysis

1. Naive Approach and its Limitations

The simplest approach is to perform an exhaustive search, such as Depth-First Search (DFS), to explore all possible paths starting from day 1 to day \(K\). However, assuming each city has an average of \(d\) outgoing roads, the total number of paths grows exponentially as \(O(d^K)\). Given the constraint \(K \le 1000\), an exhaustive search will definitely result in a Time Limit Exceeded (TLE).

2. Applying Dynamic Programming (DP)

To determine the maximum score of being in city \(v\) on day \(j\), the only information we need is “which city we were in on day \(j-1\) and what the maximum score was at that time.” We do not need to keep track of the exact path taken before that (from day 1 to day \(j-2\)).

Thus, Dynamic Programming (DP), which processes calculations step-by-step using previous optimal states, is highly effective here.

Specifically, we define the state as follows: - \(dp[j][v]\): The maximum total score accumulated up to day \(j\) when staying in city \(v\) on day \(j\) (or an invalid value like \(-1\) if unreachable).

We can stay in city \(v\) on day \(j\) only if we were in some city \(u\) on the previous day (\(j-1\)) from which there is a direct road to \(v\). Therefore, the transition formula is:

\[dp[j][v] = \max_{u \to v \text{ exists}} (dp[j-1][u]) + (P_v \times j) \bmod Q\]

3. Saving Memory (Reducing Space Complexity)

To calculate the values of \(dp[j][v]\), we only need the information from the immediate previous step, \(dp[j-1]\). Data from day \(j-2\) and earlier is no longer needed. Therefore, by maintaining only two 1D arrays of size \(N\) (“previous day’s DP table” and “today’s DP table”) and reusing them at each step, we can significantly reduce the memory usage from \(O(KN)\) to \(O(N)\).

Algorithm

1. Constructing the Reverse Graph: To quickly list the cities \(u\) that can transition to city \(v\), we create an adjacency list in_edges of incoming edges (reverse edges) for each city \(v\).

2. Initialization: Create the DP table dp for day 1. Since we can start from any city on day 1, we initialize it for all cities \(v\) as follows: $\(dp[v] = (P_v \times 1) \bmod Q\)$

3. DP Transitions (Loop from \(j = 2\) to \(K\)): At each step \(j\), prepare a new DP table next_dp (all initialized to \(-1\)). For each city \(v\), perform the following:

   • Find the maximum value max_val of dp[u] among all cities \(u\) that have an incoming edge to city \(v\) (in_edges[v]).
   • If max_val exists (i.e., is not \(-1\)), set next_dp[v] = max_val + (P_v * j) % Q.
   • At the end of the loop, update dp = next_dp.

4. Output the Answer: The maximum value in dp after completing the transitions for day \(K\), which is max(dp), will be the answer.

Complexity

Time Complexity: \(O(K(N + M))\)

• Initialization: Calculating the day 1 scores for all cities takes \(O(N)\) time.
• DP Transitions: In a single step \(j\), we iterate over all cities \(v\) and their in-degrees (the number of incoming edges). The sum of the in-degrees over all cities is equal to the total number of edges \(M\). Thus, the time complexity per step is \(O(N + M)\).
• Since we repeat this process \(K-1\) times, the overall time complexity for the transitions is \(O(K(N + M))\).

Substituting the maximum values from the constraints (\(N = 1000, M = 50000, K = 1000\)), the number of operations in the worst case is approximately \(5.1 \times 10^7\), which easily runs within the time limit even in Python.

Space Complexity: \(O(N + M)\)

• We use \(O(N + M)\) memory to store the adjacency list (reverse edges) of the graph.
• Since we only maintain two 1D arrays of length \(N\) for the DP tables, the required memory for them is \(O(N)\).
• Therefore, the overall space complexity is \(O(N + M)\), which is highly memory-efficient.

Implementation Details

• Adopting Pull DP: By using a “pull-type” DP, where we trace backward to find “which cities can transition to city \(v\)” for each city \(v\), we prevent unnecessary state updates and keep the code simple and intuitive.

• Fast I/O and Optimization: To reduce loop overhead in Python, we use sys.stdin.read to load all inputs at once. Additionally, converting the adjacency list in_edges from a list of lists to a list of tuples speeds up access within the loops.

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    Q = int(data[3])

    P = [int(x) for x in data[4 : 4 + N]]

    in_edges = [[] for _ in range(N)]
    idx = 4 + N
    for _ in range(M):
        u = int(data[idx]) - 1
        v = int(data[idx + 1]) - 1
        in_edges[v].append(u)
        idx += 2

    in_edges = [tuple(edges) for edges in in_edges]

    dp = [(p * 1) % Q for p in P]

    for j in range(2, K + 1):
        next_dp = [-1] * N
        for v in range(N):
            max_val = -1
            for u in in_edges[v]:
                if dp[u] > max_val:
                    max_val = dp[u]
            if max_val != -1:
                next_dp[v] = max_val + (P[v] * j) % Q
        dp = next_dp

    print(max(dp))


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-high.