Overview

You are given \(N\) cities and \(M\) one-way routes. You will stay in exactly one city each day for \(K\) days. Staying in city \(i\) on day \(j\) yields a score of \((P_i \times j) \bmod Q\). Under the constraint that you can only move to a city if a route exists from the city you stayed in on the previous day, the goal is to find the maximum possible total score over the \(K\) days.

Observation

First, a stay plan is a sequence of cities \(c_1, c_2, \ldots, c_K\) such that a route exists between adjacent cities in the sequence. This corresponds to a path of length \(K\) on the graph (where visiting the same city multiple times is allowed).

The key observation here is that the score obtained on day \(j\) depends only on the city on that day and the number of days elapsed. The value \((P_i \times j) \bmod Q\) does not depend at all on which cities were visited in the past. In other words, once we decide which city we are in on a given day, the score for that day is determined independently of the history.

From this, if we consider the state “the maximum total score from day \(1\) to day \(j\) when staying in city \(i\) on day \(j\),” we can see that this can be calculated solely from the states of the previous day. That is, dynamic programming (DP) can be applied.

A naive approach of “enumerating all paths” is impossible because the number of paths grows exponentially. However, with the above observation, we only need to keep track of the “current city” as the state, which greatly reduces the number of states.

Algorithm

We define the DP state as follows:

\[dp[j][i] = \text{the maximum total score from day } 1 \text{ to } j \text{ when staying in city } i \text{ on day } j\]

Initialization (Day 1): Since we can start from any city on Day 1: $\(dp[1][i] = (P_i \times 1) \bmod Q\)$

Transition (Day 2 onwards): To be in city \(b\) on day \(j\), we must have been in some “city \(a\) that has a route to city \(b\)” on the previous day \(j-1\). For each route \(a \to b\), we update: $\(dp[j][b] = \max_{a \to b \text{ exists}} \Big( dp[j-1][a] + (P_b \times j) \bmod Q \Big)\)$ It is efficient to iterate through each route and update the value at the destination end.

Answer: The maximum value among all cities on day \(K\): $\(\text{answer} = \max_{1 \le i \le N} dp[K][i]\)$

In the implementation, since \(dp[j]\) is calculated only from \(dp[j-1]\), we do not need to maintain a two-dimensional array. Instead, we can reuse just two arrays: “the previous day’s array dp” and “the current day’s array ndp” (by swapping them).

Unreachable states should be initialized with a very small value (denoted as NEG in the code), and transitions from them should be skipped. Since the problem guarantees the existence of at least one valid stay plan, the final answer will not remain NEG.

Complexity

For each day, we perform transitions by iterating through all routes (\(M\) routes) once. Repeating this for \(K\) days gives:

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

Since \(M \le 50000\) and \(K \le 1000\), the number of operations is at most around \(5 \times 10^7\), which easily runs within the time limit.

Implementation Points

• Handling Score Overflow: Since \(P_i \le 10^6\) and \(j \le 1000\), \(P_i \times j\) can be around \(10^9\), which can overflow a standard 32-bit signed int during intermediate multiplications in some environments. In the calculation of (P[b] * jj) % Q, treat jj as long long to perform the calculation using 64-bit integers. Furthermore, since the total score accumulates over \(K\) days, the DP values themselves must also be stored as long long.

• Handling Unreachable States: Set the initial value NEG to around LLONG_MIN/4, and skip transitions when dp[a] == NEG. This prevents incorrectly adding values from “non-existent paths.”

• Caution on Transition Direction: Since the routes are one-way, we should use “the previous day’s value of city \(a\)” to update “the current day’s value of city \(b\)” for the route a → b. Be careful not to reverse the direction.

• Reusing Arrays: By initializing ndp with NEG every day, updating it, and finally swapping dp and ndp via swap(dp, ndp), you can write the code concisely while saving memory.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M, K; long long Q;
    scanf("%d %d %d %lld", &N, &M, &K, &Q);
    vector<long long> P(N+1);
    for(int i=1;i<=N;i++) scanf("%lld",&P[i]);
    vector<int> A(M), B(M);
    for(int k=0;k<M;k++) scanf("%d %d",&A[k],&B[k]);

    const long long NEG = LLONG_MIN/4;
    vector<long long> dp(N+1, NEG), ndp(N+1, NEG);

    // day 1: can start anywhere
    for(int i=1;i<=N;i++){
        dp[i] = (P[i]*1LL) % Q;
    }

    for(int j=2;j<=K;j++){
        for(int i=1;i<=N;i++) ndp[i]=NEG;
        long long jj = j;
        for(int k=0;k<M;k++){
            int a=A[k], b=B[k];
            if(dp[a]==NEG) continue;
            long long cand = dp[a] + (P[b]*jj)%Q;
            if(cand > ndp[b]) ndp[b]=cand;
        }
        swap(dp,ndp);
    }

    long long ans = NEG;
    for(int i=1;i<=N;i++) ans = max(ans, dp[i]);
    printf("%lld\n", ans);
    return 0;
}

---

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