(Analysis by Benjamin Qi)

If Bessie travels for exactly $t$ days then the amount of moonies that she makes is bounded above by $1000t-t^2,$ which is negative when $t>1000.$ Thus, it suffices to keep track of the DP states $dp[x][t]$ for each $1\le x\le N, 0\le t\le 1000,$ denoting the maximum amount of moonies Bessie can make up to time $t$ if she is located at city $x$ at time $t$. The final answer will be $\max_{0\le t\le 1000}(dp[t]-Ct^2).$ This solution runs in $O(\max(m_i)\cdot (N+M)).$ time.

Mark Chen's code:

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

const int MAXN = 1005;
const int MAXT = 1005;

long long n, m, c;
long long value[MAXN];
long long dp[MAXN];

vector<pair<int, int>> edges;

int main() {
freopen("time.in","r",stdin);
freopen("time.out","w",stdout);
cin >> n >> m >> c;
for (int i = 1; i <= n; i++) {
cin >> value[i];
}
int a, b;
for (int i = 0; i < m; i++) {
cin >> a >> b;
edges.push_back(make_pair(a, b));
}
long long max_profit = 0;
memset(dp, -1, sizeof dp);
dp = 0;
for (int t = 1; t < MAXT; t++) {
int p = t % 2;
memset(dp[p], -1, sizeof dp[p]);
for (auto& e : edges) {
a = e.first;
b = e.second;
if (dp[1-p][a] >= 0) {
dp[p][b] = max(dp[p][b], dp[1-p][a] + value[b]);
}
}
max_profit = max(max_profit, dp[p] - c * t * t);
}
cout << max_profit << "\n";
}