Overview

You are given \(N\) cities and one-way routes between them. You will travel through these cities over \(K\) days. If you stay in city \(i\) on day \(j\), you receive a score of \((P_i \times j) \bmod Q\). The goal is to find the maximum possible total score over the \(K\) days.

Analysis

In this problem, we need to maximize the total score of a travel plan (a sequence of cities) over \(K\) days. If we try to enumerate all possible travel plans, there are \(N\) choices for the first day, and up to \(N\) choices for each subsequent day. This results in an overall time complexity of \(O(N^K)\), which will lead to a TLE (Time Limit Exceeded) under the constraint \(K \le 1000\).

Instead, we can maintain the “maximum total score up to day \(j\) given that we are staying in city \(i\) on day \(j\).” Let this be dp[j][i]. We can stay in city \(i\) on day \(j\) if we were in some city \(u\) on day \(j-1\) and there is a route from city \(u\) to city \(i\). Therefore, the following transition holds:

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

This approach of updating the current day’s state using only the previous day’s state is called Dynamic Programming (DP). By using DP, we can avoid redundant searches and find the maximum value efficiently.

Algorithm

1. Initialization: Since we can start at any city on day 1, we set dp[1][i] = (P_i \times 1) \bmod Q for all cities \(i\).
2. DP Table Update: Repeat the following process for \(j = 2\) to \(K\):
   • Update the current day’s DP array (dp_curr) using the previous day’s DP array (dp_prev).
   • For all routes \(u \to v\), perform dp_curr[v] = max(dp_curr[v], dp_prev[u]). Note that we do not add the current day’s score at this stage.
   • For all cities \(i\), if they are reachable, add the current day’s score: dp_curr[i] += (P_i \times j) \bmod Q.
3. Output the Answer: The maximum value in the DP array on day \(K\) is the maximum total score.

To optimize memory usage, instead of storing the DP arrays for all \(K\) days, we only maintain two arrays—one for the previous day and one for the current day (rolling array technique)—thereby reducing the space complexity.

Complexity

• Time Complexity: \(O(N + K \times M)\)
  • It takes \(O(N)\) for initialization, \(O(M)\) to check all edges each day, and \(O(N)\) to add the scores each day. Thus, the overall time complexity is \(O(N + K \times (M + N))\), which is fast enough under the given constraints.
• Space Complexity: \(O(N + M)\)
  • We use \(O(N + M)\) memory for the graph’s adjacency list and \(O(N)\) for the DP arrays.

Implementation Details

• Timing of Score Addition: Add the current day’s score \((P_v \times j) \bmod Q\) only after determining whether city \(v\) is reachable. Care must be taken not to add scores to unreachable cities (where the value in dp_curr remains \(-\infty\)).

• Initial Values: To represent unreachable states, initialize the DP table with a sufficiently small value (e.g., \(-10^{18}\)).

• Input Speedup in Python: Since the input size can be large, use sys.stdin.readline to speed up input reading.

  Source Code

import sys

def solve():
    input = sys.stdin.readline
    N, M, K, Q = map(int, input().split())
    P = list(map(int, input().split()))
    
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u - 1].append(v - 1)
    
    for i in range(N):
        adj[i] = tuple(adj[i])
        
    INF = 10**18
    dp_prev = [-INF] * N
    for i in range(N):
        dp_prev[i] = (P[i] * 1) % Q
        
    for j in range(2, K + 1):
        dp_curr = [-INF] * N
        for u in range(N):
            val = dp_prev[u]
            if val == -INF:
                continue
            for v in adj[u]:
                if val > dp_curr[v]:
                    dp_curr[v] = val
        
        mul = j
        for i in range(N):
            if dp_curr[i] != -INF:
                dp_curr[i] += (P[i] * mul) % Q
                
        dp_prev = dp_curr
        
    print(max(dp_prev))

if __name__ == '__main__':
    solve()

This editorial was generated by or-glm5.2-high.