USACO 2020 January Contest, Gold Problem 1. Time is Mooney

USACO 2020 January Contest, Gold Problem 1. Time is Mooney

Bessie is conducting a business trip in Bovinia, where there are NN (2N10002≤N≤1000) cities labeled 1N1…N connected by MM (1M20001≤M≤2000) one-way roads. Every time Bessie visits city i,i, Bessie earns mimi moonies (0mi10000≤mi≤1000). Starting at city 1 Bessie wants to visit cities to make as much mooney as she can, ending back at city 1. To avoid confusion, m1=0.m1=0.

Mooving between two cities via a road takes one day. Preparing for the trip is expensive; it costs CT2C⋅T2 moonies to travel for TT days (1C10001≤C≤1000).

What is the maximum amount of moonies Bessie can make in one trip? Note that it may be optimal for Bessie to visit no cities aside from city 1, in which case the answer would be zero.



The first line contains three integers NNMM, and CC.The second line contains the NN integers m1,m2,mNm1,m2,…mN.

The next MM lines each contain two space-separated integers aa and bb (aba≠b) denoting a one-way road from city aa to city bb.


OUTPUT FORMAT (file time.out):

A single line with the answer.



3 3 1
0 10 20
1 2
2 3
3 1



The optimal trip is 1231231.1→2→3→1→2→3→1. Bessie makes 10+20+10+20162=2410+20+10+20−1⋅62=24 moonies in total.


Problem credits: Richard Peng and Mark Gordon

<h3> USACO 2020 January Contest, Gold Problem 1. Time is Mooney 题解(翰林国际教育提供,仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>

(Analysis by Benjamin Qi)

If Bessie travels for exactly tt days then the amount of moonies that she makes is bounded above by 1000tt2,1000t−t2, which is negative when t>1000.t>1000. Thus, it suffices to keep track of the DP states dp[x][t]dp[x][t] for each 1xN,0t1000,1≤x≤N,0≤t≤1000, denoting the maximum amount of moonies Bessie can make up to time tt if she is located at city xx at time tt. The final answer will be max0t1000(dp[1][t]Ct2).max0≤t≤1000(dp[1][t]−Ct2). This solution runs in O(max(mi)(N+M)).O(max(mi)⋅(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[2][MAXN];
vector<pair<int, int>> edges;
int main() {
	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][1] = 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][1] - c * t * t);
	cout << max_profit << "\n";