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[1010][1010];

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;
}