Analysis: Pogo-Cow, by Brian Dean

This problem is solved by dynamic programming. Let us focus on the best left-to-right solution; the same approach will also find the best right-to-left solution, after which we need to take the better of the two. Let DP[i][j] denote the maximum value we can collect if we start at target i and our next hop lands on target j. We can write this recursively as DP[i][j] = value of ith target + max DP[j][k], where k ranges over all targets such that the distance from j to k is at least as large as the distance from i to j. This formulation involves solving O(N^2) subproblems, each of which takes O(N) time to solve, for a total of O(N^3) time. Unfortunately, O(N^3) is a bit too slow for the limits given in this problem, but we can speed our algorithm up to run in only O(N^2) time by keeping running maximums of the form DP[j][k...], allowing us to solve each subproblem in only O(1) time.

Mark Gordon's solution is below.

```#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

int DP;

int main() {
freopen("pogocow.in", "r", stdin);
freopen("pogocow.out", "w", stdout);

int N; cin >> N;

vector<pair<int, int> > A(N);
for(int i = 0; i < N; i++)
cin >> A[i].first >> A[i].second;
sort(A.begin(), A.end());

int result = 0;
for(int ii = 0; ii < 2; ii++) {
for(int i = N - 1; i >= 0; i--) {
int k = N;
int val = 0;
for(int j = 0; j <= i; j++) {
while(k - 1 > i &&
A[k - 1].first - A[i].first >= A[i].first - A[j].first) {
--k;
val = max(val, A[k].second + DP[k][i]);
}
DP[i][j] = val;
}
result = max(result, A[i].second + val);
}
for(int i = 0; i < N; i++) {
A[i].first = -A[i].first;
}
reverse(A.begin(), A.end());
}

cout << result << endl;
return 0;
}
```