Overview

This problem asks us to simulate movement on a directed graph for \(K\) days and maximize the total score obtained based on the city we stay in each day (calculated from the day number and a base value for each city).

Analysis

In this problem, we need to find a travel plan for \(K\) days (a path of length \(K\) on a directed graph). If we search all valid travel plans exhaustively, the number of path combinations will be huge, resulting in TLE (Time Limit Exceeded).

Therefore, we consider using Dynamic Programming (DP) to efficiently find the maximum value. In DP, we maintain the “maximum score when staying in city \(i\) on day \(j\)” and compute the optimal solution sequentially starting from day \(1\).

Algorithm

1. DP State Definition: dp[j][i] = the maximum total score from day \(1\) to day \(j\) when staying in city \(i\) on day \(j\). Unreachable states are represented by a value such as -1.

2. Initial State: Since we can start from any city on day \(1\), we set dp[1][i] = P_i % Q for each city \(i\).

3. Transitions: For the calculation of day \(j\) (\(2 \leq j \leq K\)), we consider each transition \(u \to v\) in the graph. This represents the transition “staying in city \(u\) on day \(j-1\) and moving to city \(v\) on day \(j\)”. Since the score for city \(v\) on day \(j\) is given by \((P_v \times j) \bmod Q\), we transition as follows:

   dp[j][v] = max(dp[j][v], dp[j-1][u] + (P_v * j) % Q)
   

   However, we must ensure that dp[j-1][u] != -1 (city \(u\) was reachable on the previous day).

4. Finding the Answer: The maximum value in the dp table for staying in any city on day \(K\) will be the answer.

5. Space Optimization: Since the dp array only requires the information of day \(j\) and day \(j-1\) to compute, we can reduce the memory usage to \(O(N)\) by keeping only two arrays and swapping them after each update.

Complexity

• Time Complexity: \(O(K M)\) For each day (\(K\) times), we check the transitions of all edges (\(M\) edges), resulting in \(O(K M)\). Under the constraints, this is around \(10^3 \times 5 \times 10^4 = 5 \times 10^7\) operations, which easily fits within the time limit in C++.
• Space Complexity: \(O(N + M)\) We need space to store two DP arrays and the list of edges.

Implementation Points

• In the score calculation P_v * j, since \(P_v \leq 10^6\) and \(j \leq 1000\), the product can be up to \(10^9\). Since the total score can easily overflow a standard 32-bit signed int type, you should use a 64-bit integer (long long type in C++) for the calculations.

• When updating the DP array, initialize it with -1 to indicate that the city is unreachable, and make sure to check if a city is reachable before transitioning to avoid bugs.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M, K, Q;
    if (!(cin >> N >> M >> K >> Q)) return 0;
    
    vector<long long> P(N);
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
    }
    
    vector<pair<int, int>> edges(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].first >> edges[i].second;
        --edges[i].first;
        --edges[i].second;
    }
    
    vector<long long> dp_prev(N, -1);
    vector<long long> dp_curr(N, -1);
    
    for (int i = 0; i < N; ++i) {
        dp_prev[i] = P[i] % Q;
    }
    
    for (int j = 2; j <= K; ++j) {
        fill(dp_curr.begin(), dp_curr.end(), -1);
        for (auto& e : edges) {
            int u = e.first;
            int v = e.second;
            if (dp_prev[u] != -1) {
                long long score_mod = (P[v] * j) % Q;
                long long new_score = dp_prev[u] + score_mod;
                if (new_score > dp_curr[v]) {
                    dp_curr[v] = new_score;
                }
            }
        }
        swap(dp_prev, dp_curr);
    }
    
    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        if (dp_prev[i] > ans) {
            ans = dp_prev[i];
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

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