Overview

For \(K\) days, we need to choose a city to stay in each day, moving along directed edges between consecutive days.
Since the score for each city on each day is determined, we can find the maximum score using dynamic programming where the state is “which city we are in on which day”.

Analysis

A travel plan is a sequence of cities of length \(K\): \(c_1, c_2, \ldots, c_K\).
If we simply try all possible travel plans, since there are up to \(N\) choices for each day, there would be \(N^K\) combinations in the worst case, which is far too slow to run in time.

Therefore, we can think as follows:

• It is sufficient to know the maximum score when we are in city \(i\) on day \(j\).
• To move to city \(b\) on day \(j+1\), we must have been in city \(a\) on the previous day, and the directed edge \(a \to b\) must exist.
• In other words, we can update the state for the next day by transitioning from the state of the previous day along the edges.

We define the state as follows:

\[ dp[i] = \text{maximum score when staying in city } i \text{ on the current day} \]

Since we can start from any city on the first day,

\[ dp[i] = (P_i \times 1) \bmod Q \]

From the second day onwards, for each edge \(a \to b\), if it was possible to be in city \(a\) on the previous day, we can move to city \(b\):

\[ ndp[b] = \max(ndp[b], dp[a]) \]

After that, we add the score obtained by staying in city \(b\) on day \(j\):

\[ (P_b \times j) \bmod Q \]

Checking all pairs of cities \((a, b)\) would take \(O(KN^2)\) time. With \(N, K \leq 1000\), this can be up to \(10^9\) operations, which is too slow.
However, since the only valid moves are along the \(M\) given edges, we can iterate over the edge list to achieve a time complexity of \(O(KM)\).

Algorithm

Let \(dp_j[i]\) be “the maximum total score when staying in city \(i\) on day \(j\)”.

The initial values are:

\[ dp_1[i] = P_i \bmod Q \]

The transition for each edge \(a \to b\) is:

\[ dp_j[b] = \max(dp_j[b], dp_{j-1}[a] + ((P_b \times j) \bmod Q)) \]

In the implementation, since we only need the values of the previous day to compute the current day’s values, we only need to maintain two arrays.

The specific flow is as follows:

1. Initialize dp[i] with the score of city \(i\) on the first day.
2. Loop day from \(2\) to \(K\):
   • Initialize ndp with a sufficiently small value representing “unreachable”.
   • Iterate through all edges \(a \to b\):
     • If dp[a] is reachable, update ndp[b].
   • For each city \(i\), if it is reachable, add the score for staying in it on that day.
   • Swap dp and ndp.
3. The answer is the maximum value in dp on the final day.

Complexity

• Time Complexity: \(O(K(M+N))\)
  • For each day, we iterate through all \(M\) edges and then add the score to all \(N\) cities.
• Space Complexity: \(O(N+M)\)
  • We only store the DP arrays for the current day and the next day.
  • We store the list of \(M\) edges.

Implementation Details

To represent unreachable states, we define a sufficiently small value NEG.

const long long NEG = -(1LL << 60);

In transitions using edges, we ignore the transition if the city a on the previous day was unreachable.

if (dp[a] == NEG) continue;

Also, since the total score can be large, we should use long long.

If \(K=1\), no transitions are performed, and the maximum score on the first day is directly the answer.

Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    long long Q;
    cin >> N >> M >> K >> Q;

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

    vector<pair<int, int>> edges;
    edges.reserve(M);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        edges.emplace_back(a, b);
    }

    const long long NEG = -(1LL << 60);

    vector<long long> dp(N, NEG), ndp(N, NEG);

    for (int i = 0; i < N; i++) {
        dp[i] = (P[i] * 1) % Q;
    }

    for (int day = 2; day <= K; day++) {
        fill(ndp.begin(), ndp.end(), NEG);

        for (auto [a, b] : edges) {
            if (dp[a] == NEG) continue;
            ndp[b] = max(ndp[b], dp[a]);
        }

        for (int i = 0; i < N; i++) {
            if (ndp[i] != NEG) {
                ndp[i] += (P[i] * day) % Q;
            }
        }

        dp.swap(ndp);
    }

    long long ans = *max_element(dp.begin(), dp.end());
    cout << ans << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.