Overview

This problem asks us to maximize the total score by choosing a city to stay in each day while following a valid movement route.
We can solve this using Dynamic Programming (DP) where the state is “the maximum score when we are at city \(i\) on day \(j\)”.

Analysis

Since the itinerary is a sequence of cities of length \(K\), enumerating all possible choices would result in up to \(N^K\) combinations, which is clearly too slow.

Instead, we can think as follows:

• We are at city \(v\) on day \(j\).
• On the previous day \(j-1\), we must have been at some city \(u\) from which we can move to city \(v\).

In other words, to reach city \(v\) on day \(j\), we must come from a city \(u\) such that there is a directed edge \(u \to v\).

Therefore, if we define

\[ dp[j][v] = \text{maximum score when at city } v \text{ on day } j \]

the DP transition is as follows:

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

Since we can start at any city on the first day, the base case is:

\[ dp[1][v] = P_v \bmod Q \]

The key observation here is that we only need to consider the “incoming edges to city \(v\)”.
Checking all pairs of cities would take \(O(KN^2)\) time, which is too slow. However, by only considering the edges that actually exist, we can reduce the time complexity to \(O(KM)\).

Furthermore, to compute \(dp[j]\), we only need the values from \(dp[j-1]\). Thus, instead of a 2D array, we can reuse a 1D array to optimize space.

Algorithm

For each city \(v\), we construct a list of “cities that can transition to \(v\)”.

For example, if there is an edge \(a \to b\), we add a to rev[b].

We define the DP as follows:

• dp[v]: the maximum score when at city \(v\) on the current day.

The initial state is for day 1:

\[ dp[v] = P_v \bmod Q \]

After that, we update the DP state sequentially from day 2 to day \(K\).

Let the score of city \(v\) on day \(j\) be:

\[ score(v, j) = (P_v \times j) \bmod Q \]

Then, the transition is:

\[ new\_dp[v] = \max_{u \in rev[v]} dp[u] + score(v, j) \]

Finally, since we can end up in any city on day \(K\), we output:

\[ \max_v dp[v] \]

In the implementation, although we can compute \(P_v \times j\) from scratch each time, the code instead updates each city’s score incrementally from the previous day:

\[ (P_v \times j) \bmod Q = ((P_v \times (j-1)) \bmod Q + P_v) \bmod Q \]

Using this property, we maintain the current day’s score of city \(v\) in weights[v].

Complexity

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

Given \(N \leq 1000\), \(M \leq 50000\), and \(K \leq 1000\), this will easily run within the time limit.

Key Implementation Points

• Since we can start from any city on the first day, we initialize dp = pmod[:].

• To be in city \(v\) on day 2 or later, there must be an incoming edge to city \(v\). Thus, we manage incoming edges using rev[v].

• Unreachable states are represented by a very small value, NEG = -10**18.

• If \(K=1\), we do not need to consider any transitions, so we simply output max(P_i % Q).

• By updating weights[v] daily, we efficiently compute \((P_v \times j) \bmod Q\).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, K, Q = data[0], data[1], data[2], data[3]

    P = data[4:4 + N]
    pmod = [x % Q for x in P]

    rev = [[] for _ in range(N)]
    idx = 4 + N
    for _ in range(M):
        a = data[idx] - 1
        b = data[idx + 1] - 1
        idx += 2
        rev[b].append(a)

    if K == 1:
        print(max(pmod))
        return

    nonempty = [(i, rev[i]) for i in range(N) if rev[i]]

    NEG = -10**18
    dp = pmod[:]
    weights = pmod[:]

    n = N
    q = Q
    pm = pmod
    ne = nonempty
    neg = NEG

    for _ in range(K - 1):
        old = dp
        ndp = [neg] * n
        wt = weights

        for i, ins in ne:
            wi = wt[i] + pm[i]
            if wi >= q:
                wi -= q
            wt[i] = wi

            mx = neg
            for u in ins:
                val = old[u]
                if val > mx:
                    mx = val

            ndp[i] = mx + wi

        dp = ndp

    print(max(dp))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.