Overview

Given \(N\) cities and \(M\) one-way routes, we stay in exactly one city on each of the \(K\) days. Staying in city \(i\) on day \(j\) yields a score of \((P_i \times j) \bmod Q\). Under the constraint that we must move along the routes between adjacent days, we want to find the maximum total score over the \(K\) days.

Analysis

First, the score \((P_i \times j) \bmod Q\) obtained on each day depends only on “which city we are in on that day” and does not depend on our past travel history. In other words, the score on day \(j\) is determined solely by the pair of “city” and “day”.

From this, we can see a typical Dynamic Programming (DP) structure: if we determine which city we are in on a certain day, we only need to record the maximum score obtained up to that point.

Specifically, let us define the following value:

\(dp_j[i]\) = the maximum total score from day 1 to day \(j\) among all travel plans where we stay in city \(i\) on day \(j\).

A naive approach of “enumerating all travel plans” would cause the total number of plans to grow exponentially, which is far too slow. However, by using the DP above, the state of day \(j\) can be computed using only the transitions from the state of day \(j-1\), allowing us to solve it efficiently.

The key is the direction of transitions. If we are in city \(u\) on day \(j-1\) and there is a route \(u \to v\), we can be in city \(v\) on day \(j\). In this case, we can update:

\[dp_j[v] = \max\Bigl(dp_j[v],\; dp_{j-1}[u] + (P_v \times j \bmod Q)\Bigr)\]

In other words, the process takes the form of iterating through each route one by one and updating the value at the destination from the value at the starting point.

Algorithm

1. Initialization (Day 1): Since we can start from any city on day 1, for all cities \(i\), we set: $\(dp_1[i] = (P_i \times 1) \bmod Q = P_i \bmod Q\)$

2. Transitions (Day 2 onwards): For \(j = 2, 3, \ldots, K\), perform the following:

   • First, precompute the score obtained when staying in each city \(v\) on day \(j\): \(sc[v] = (P_v \times j) \bmod Q\).
   • Initialize the DP array \(ndp\) for day \(j\) with a negative value representing “unreachable”.
   • For all routes \((u, v)\), if \(dp_{j-1}[u]\) is reachable (non-negative): $\(ndp[v] \leftarrow \max(ndp[v],\; dp_{j-1}[u] + sc[v])\)$
   • Set \(dp_j\) to \(ndp\).

3. Answer: Finally, the maximum value in the DP array of day \(K\), \(\max_i dp_K[i]\), is the answer.

Handling Unreachable States: Depending on how the routes are connected, there may be cities that cannot be visited on certain days. Therefore, we mark “unvisited cities” with a negative value (-1 in the code), and if the source state is unreachable, we skip that transition. This prevents us from incorrectly counting invalid plans. Since the problem guarantees the existence of at least one valid plan, there will be at least one non-negative value remaining on day \(K\).

Complexity

• Time Complexity: \(O(N + K \times (N + M))\)
  • For each day, calculating the scores takes \(O(N)\), and transitioning by scanning all routes takes \(O(M)\). We repeat this for \(K\) days. Even in the worst-case scenario, \(K \times (N + M) \approx 1000 \times 51000 \approx 5 \times 10^7\), which is fast enough.
• Space Complexity: \(O(N + M)\)
  • We only need to store the DP array for one day (and the next day), and storing the route information takes \(O(M)\).

Implementation Details

• Reusing DP Arrays: Once \(dp_j\) is calculated, \(dp_{j-1}\) is no longer needed. Thus, keeping only two arrays (or creating a new one each time) is sufficient. You do not need to store the DP arrays for all \(K\) days, which saves memory.

• Precomputing Scores: The score for day \(j\), \((P_v \times j) \bmod Q\), should be calculated only once for each city \(v\) and stored in an array \(sc\). This avoids repeating the same calculation inside the transition loop.

• Transitioning Route-by-Route: Instead of “finding incoming routes for each destination”, you can write it as “iterating through all routes one by one and updating the destination from the starting city”. This simplifies the implementation as you do not need to build an adjacency list.

• Fast I/O: Since \(N, M, K\) can be up to \(1000\) to \(50000\), reading all inputs at once using sys.stdin.buffer.read() speeds up the input processing, making it easily pass within the time limit even in Python.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); M = int(data[idx+1]); K = int(data[idx+2]); Q = int(data[idx+3])
    idx += 4
    P = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = int(data[idx]); idx += 1
    edges = [(0, 0)] * M
    for k in range(M):
        u = int(data[idx]); v = int(data[idx+1]); idx += 2
        edges[k] = (u, v)

    NEG = -1
    dp = [NEG] * (N + 1)
    for i in range(1, N + 1):
        dp[i] = P[i] % Q

    for j in range(2, K + 1):
        sc = [0] * (N + 1)
        for i in range(1, N + 1):
            sc[i] = (P[i] * j) % Q
        ndp = [NEG] * (N + 1)
        for (u, v) in edges:
            du = dp[u]
            if du >= 0:
                val = du + sc[v]
                if val > ndp[v]:
                    ndp[v] = val
        dp = ndp

    print(max(dp))

main()

This editorial was generated by claude4.8opus-high.