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