Overview

This problem asks us to maximize the total score obtained at each step along a path of length \(K\) on a given directed graph. The score for staying in city \(i\) on day \(j\) is defined as \((P_i \times j) \bmod Q\).

By using dynamic programming (DP), we can efficiently find the maximum score.

Analysis

Applying Dynamic Programming (DP)

When deciding which city to stay in on day \(j\), the only information that matters from previous actions is “which city we were in on day \(j-1\).” The path taken before that has no effect on subsequent moves or scores. For problems like this, where past decisions are summarized entirely by the current state, dynamic programming (DP) is extremely effective.

We define the DP table as follows:

• \(dp[j][i]\): The maximum total score when staying in city \(i\) on day \(j\) (set to an invalid value such as \(-\infty\) if unreachable)

Designing the Transition Formula

Since we can start from any city on day \(1\), the initial state (\(j=1\)) is as follows: $\(dp[1][i] = (P_i \times 1) \bmod Q \quad (1 \leq i \leq N)\)$

We consider the transition for day \(j\) (\(2 \leq j \leq K\)). To stay in city \(v\) on day \(j\), we must have been in some city \(u\) on day \(j-1\) such that a route from \(u\) to \(v\) exists. Therefore, for all cities \(u\) where a directed edge \(u \to v\) exists, we look up the maximum score from the previous day.

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

If no edges entering city \(v\) exist, or if all source cities \(u\) are unreachable (\(dp[j-1][u] = -\infty\)), then \(dp[j][v] = -\infty\).

Memory Optimization

Naively preparing a 2D array \(dp[K][N]\) would result in \(O(KN)\) space complexity. However, looking at the transition formula, to compute the values for day \(j\), we only need the values from day \(j-1\). Therefore, by preparing only two 1D arrays of size \(N+1\) (dp and next_dp) and alternately swapping (reusing) them at each step, we can reduce the space complexity to \(O(N)\).

Algorithm

1. Building the reverse adjacency list of the graph: For each city \(v\), to quickly retrieve which cities \(u\) can transition to it, we store the directed edge \(u \to v\) as a “reverse edge from endpoint \(v\) to starting point \(u\).”
2. Initializing the DP table: Create a dp array of size \(N+1\) and initialize it with \(dp[i] = (P_i \times 1) \bmod Q\) for each city \(i\).
3. DP transitions (loop from \(j = 2\) to \(K\)):
   • Initialize next_dp, which holds the next day’s scores, with all invalid values (such as \(-1\)).
   • For each city \(v\), scan the source cities \(u\) (cities \(u\) where an edge \(u \to v\) exists) and find \(\max(dp[u])\).
   • If a maximum value exists, set next_dp[v] = \max(dp[u]) + (P_v \times j) \bmod Q.
   • Update dp with the contents of next_dp.
4. Outputting the answer: The maximum value in the dp array after the loop for day \(K\) completes is the desired maximum score.

Complexity

Time Complexity

• Initialization: \(O(N)\)
• DP transitions: At each step \(j\) (from \(2\) to \(K\), a total of \(K-1\) times), we scan all cities \(v\) and the edges \(u \to v\) entering each city. The sum of in-degrees of all cities equals the total number of edges \(M\). Therefore, the time per step for transitions is \(O(N + M)\). Repeating this \(K-1\) times, the overall complexity of the DP is \(O(K(N + M))\).

The overall time complexity is \(O(K(N + M))\). Under the constraints (\(N, K \leq 2000, M \leq 100000\)), the worst case involves approximately \(2000 \times 102000 \approx 2 \times 10^8\) operations, which is well within the time limit (typically 2 seconds) for fast languages like C++.

Space Complexity

• Storing the graph: \(O(N + M)\)
• DP table (two 1D arrays): \(O(N)\)

The overall space complexity is \(O(N + M)\), which is very comfortable with respect to the memory limit.

Implementation Tips

Speeding Up Adjacency Lists with 1D Arrays (CSR Format)

When using std::vector<std::vector<int>> in C++ to represent adjacency lists, overhead from dynamic memory allocation and pointer dereferencing occurs, which can slow down execution time.

The presented code uses a technique similar to CSR (Compressed Sparse Row) format, representing the adjacency list using a 1D array. 1. Count the in-degree deg of each vertex. 2. Compute the prefix sum head of deg. This determines which index range (from head[v] to head[v+1]) in the 1D array to stores the edge information entering each vertex \(v\). 3. Actually store the starting points u of edges at the appropriate positions in the array to.

This optimization places memory in contiguous regions, dramatically improving cache efficiency, and can significantly reduce execution time.

Source Code

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

using namespace std;

const long long INF = -1LL;

struct Edge {
    int u, v;
};

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, K;
    long long Q;
    if (!(cin >> N >> M >> K >> Q)) return 0;

    vector<long long> P(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> P[i];
    }

    vector<Edge> edges(M);
    vector<int> deg(N + 2, 0);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].u >> edges[i].v;
        deg[edges[i].v + 1]++;
    }

    // 2次元vectorの代わりに1次元配列で隣接リスト（入次数側）を表現する
    vector<int> head(N + 2, 0);
    for (int i = 1; i <= N + 1; ++i) {
        head[i] = head[i - 1] + deg[i];
    }

    vector<int> to(M);
    vector<int> cur = head;
    for (int i = 0; i < M; ++i) {
        to[cur[edges[i].v]++] = edges[i].u;
    }

    vector<long long> dp(N + 1, INF);
    for (int i = 1; i <= N; ++i) {
        dp[i] = (P[i] * 1) % Q;
    }

    vector<long long> next_dp(N + 1);

    for (int j = 2; j <= K; ++j) {
        fill(next_dp.begin(), next_dp.end(), INF);
        for (int v = 1; v <= N; ++v) {
            long long max_prev = INF;
            int start = head[v];
            int end = head[v + 1];
            for (int idx = start; idx < end; ++idx) {
                int u = to[idx];
                if (dp[u] > max_prev) {
                    max_prev = dp[u];
                }
            }
            if (max_prev != INF) {
                next_dp[v] = max_prev + (P[v] * j) % Q;
            }
        }
        swap(dp, next_dp);
    }

    long long ans = INF;
    for (int i = 1; i <= N; ++i) {
        if (dp[i] > ans) {
            ans = dp[i];
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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