Overview

In this problem, given a base score that changes daily and a set of one-way travel routes, we need to plan a stay from Day 1 to Day \(K\) to maximize the total score obtained.

By using Dynamic Programming (DP), we can efficiently find the optimal solution within the time limit.

Analysis

1. State Definition

When considering the movement over \(K\) days, suppose we are staying in city \(v\) on day \(j\). In this case, the cities we can move to on the next day, \(j+1\), are only those to which a direct travel route exists from city \(v\). In addition, the formula for calculating the score obtained changes as the days progress.

Since the “current state (which city we are in on which day)” directly affects the next choices and the score obtained, we define the following Dynamic Programming (DP) table:

• \(dp[j][v]\): The maximum total score from Day 1 to Day \(j\) when staying in city \(v\) on Day \(j\) (or an invalid value such as \(-1\) if unreachable).

2. Transition Logic

To stay in city \(v\) on Day \(j\), on the previous day (Day \(j-1\)), we must have stayed in some city \(u\) from which there is a direct route to city \(v\).

Therefore, for all cities \(u\) that have a travel route to city \(v\) (i.e., there exists an edge \(u \to v\)), we find the maximum value of the total score up to the previous day, \(dp[j-1][u]\).

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

However, if there is no city \(u\) where we could have stayed on the previous day (or if all \(dp[j-1][u]\) are the invalid value \(-1\)), we cannot stay in city \(v\) on Day \(j\), so \(dp[j][v] = -1\).

3. Space Complexity Optimization

If we straightforwardly prepare a 2D array of size \(K \times N\), the space complexity will be \(O(K \times N)\). However, the only information needed to calculate the states for Day \(j\) is the states of Day \(j-1\). Therefore, by reusing two 1D arrays of size \(N\)—the DP table for the previous day (dp) and the DP table for the day currently being calculated (next_dp)—we can reduce the space complexity to \(O(N)\).

Algorithm

1. Constructing the Reverse Graph To efficiently find the cities \(u\) that can transition to city \(v\), we create an adjacency list adj_rev that stores the given travel routes in the reverse direction.

   • When a route \(u \to v\) is given, we add \(u\) to adj_rev[v].

2. Initialization (Day 1) On Day 1, we can start from any city.

   • For all cities \(i\) (\(1 \leq i \leq N\)), we set \(dp[i] = (P_i \times 1) \bmod Q\).

3. DP Transitions (from Day 2 to Day \(K\)) For \(j = 2, 3, \ldots, K\), perform the following process:

   • Initialize a new array next_dp entirely with \(-1\).
   • For each city \(v\), examine all transition sources \(u\) contained in adj_rev[v].
   • Find the maximum value \(max\_prev\) among the valid transition sources (\(dp[u] \neq -1\)).
   • If a valid transition source exists, set next_dp[v] = max_prev + (P_v * j) % Q.
   • Update dp with next_dp.

4. Outputting the Answer Output the maximum value in the final dp array (the states on Day \(K\)).

Complexity

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

  • For each day \(j\) (from \(2\) to \(K\)), we explore all cities \(v\) and their transition sources \(u\). The total number of transitions checked is equal to the total number of edges \(M\) in the reverse graph.
  • Thus, the time required for transitions per day is \(O(N + M)\).
  • Since we repeat this for \(K\) days, the overall time complexity is \(O(K(N + M))\).
  • Under the constraints (\(N \leq 1000, M \leq 50000, K \leq 1000\)), the number of operations in the worst case is approximately \(5 \times 10^7\), which is well within the execution time limit.

• Space Complexity: \(O(N + M)\)

  • We use \(O(N + M)\) memory for the adjacency list storing the reverse graph.
  • The DP tables only require holding two arrays of size \(N+1\), which takes \(O(N)\) space.
  • The overall space complexity is \(O(N + M)\), which runs with very low memory consumption.

Key Implementation Details

• Using a Reverse Graph: By constructing a reverse adjacency list adj_rev to directly reference “where we can come from to reach city \(v\)” instead of “where we can go from city \(u\)”, we can avoid redundant searches and make the transitions simple and fast.

• Propagation of Unreachable States: We represent initial values and states that cannot be transitioned to as -1. By checking that dp[u] != -1 during transitions, we correctly exclude impossible travel plans (plans where the travel route is cut off midway).

• Optimization with std::move: In C++, by writing dp = move(next_dp), we can update the array by just swapping pointers without copying the array elements, which further reduces execution time.

  Source Code

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

using namespace std;

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<vector<int>> adj_rev(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj_rev[v].push_back(u);
    }

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

    for (int j = 2; j <= K; ++j) {
        vector<long long> next_dp(N + 1, -1);
        for (int v = 1; v <= N; ++v) {
            long long max_prev = -1;
            for (int u : adj_rev[v]) {
                if (dp[u] != -1) {
                    max_prev = max(max_prev, dp[u]);
                }
            }
            if (max_prev != -1) {
                next_dp[v] = max_prev + (P[v] * j) % Q;
            }
        }
        dp = move(next_dp);
    }

    long long ans = -1;
    for (int i = 1; i <= N; ++i) {
        ans = max(ans, dp[i]);
    }

    cout << ans << "\n";

    return 0;
}

---

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