USACO 2013 November Contest, Silver Problem 3. Pogo-Cow

http://www.usaco.org/index.php?page=viewproblem2&cpid=345

Main idea : DP

note that Bessie can jump to the positive infinite or negative infinite

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <utility>
#include <algorithm>
#include <cassert>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;
const int MAX_N = 1006;
const LL INF = 1e17 + 6;
const int oo = 1e9 + 7;

LL dp[MAX_N][MAX_N];
LL mx[MAX_N][MAX_N];
pii a[MAX_N];

LL dis(LL i,LL j) {
 if (i<1) return INF;
 return a[j].first - a[i].first;
}

int main () {
 if (fopen("pogocow.in","r")) {
     freopen("pogocow.in","r",stdin);
     freopen("pogocow.out","w",stdout);
    }
 int n;
 while (scanf("%d",&n) != EOF) {
     for (int x=0;n>=x;x++) {
         for (int y=0;n>=y;y++) {
             dp[x][y] = -INF;
             mx[x][y] = -INF;
            }
        }
     for (int x=1;n>=x;x++) {
         int i,j;
         scanf("%d %d",&i,&j);
         a[x] = make_pair(i,j);
        }
     sort(a+1,a+n+1);
     for (int x=1;n>=x;x++) {
         dp[x][0] = a[x].second;
         mx[x][0] = a[x].second;
        }
     for (int i=1;n>=i;i++) {
         for (int j=1;n>=j;j++) {
             if (i-j<1) break;
             int t=i-j;
             int L=-1,R=n+1;
             while (R-L != 1) {
                 int mid=(L+R)>>1;
                 if (dis(t-mid,t) <= dis(t,i)) L=mid;
                 else R=mid;
                }
//             cout<<"i = "<<i<<" , j=  "<<j<<" , L = "<<L<<endl;
             assert(L!=-1);
             if (L==-1) dp[i][j] = -INF;
             else dp[i][j] = mx[t][L] + a[i].second;
            }
         mx[i][0] = dp[i][0];
         int t=0;
         for (int j=1;n>=j;j++) {
             if (dp[i][j] == -INF) {
//                 mx[i][j] = mx[i][t];
                 continue;
                }
             mx[i][j] = max(dp[i][j] , mx[i][t]);
             t=j;
            }
        }
//     cout<<"Mx :\n";
//     for (int i=0;n>=i;i++) {
//         for (int j=0;n>=j;j++) {
//             cout<<(mx[i][j] == -INF?-1:mx[i][j])<<' ';
//            }
//         cout<<endl;
//        }
//     cout<<endl;
     LL ans=-INF;
     for (int i=0;n>=i;i++) {
         for (int j=0;n>=j;j++) {
//             cout<<(dp[i][j] == -INF?-1:dp[i][j])<<' ';
             ans = max(ans,dp[i][j]);
            }
//         cout<<endl;
        }
        //above is 順時針
        //下面��逆時針
     for (int x=0;n>=x;x++) {
         for (int y=0;n>=y;y++) {
             dp[x][y] = -INF;
             mx[x][y] = -INF;
            }
        }
     for (int x=1;n>=x;x++) {
         int i,j;
//         scanf("%d %d",&i,&j);
         a[x] = make_pair(-a[x].first+oo,a[x].second);
        }
     sort(a+1,a+n+1);
     for (int x=1;n>=x;x++) {
         dp[x][0] = a[x].second;
         mx[x][0] = a[x].second;
        }
     for (int i=1;n>=i;i++) {
         for (int j=1;n>=j;j++) {
             if (i-j<1) break;
             int t=i-j;
             int L=-1,R=n+1;
             while (R-L != 1) {
                 int mid=(L+R)>>1;
                 if (dis(t-mid,t) <= dis(t,i)) L=mid;
                 else R=mid;
                }
//             cout<<"i = "<<i<<" , j=  "<<j<<" , L = "<<L<<endl;
             assert(L!=-1);
             if (L==-1) dp[i][j] = -INF;
             else dp[i][j] = mx[t][L] + a[i].second;
            }
         mx[i][0] = dp[i][0];
         int t=0;
         for (int j=1;n>=j;j++) {
             if (dp[i][j] == -INF) {
//                 mx[i][j] = mx[i][t];
                 continue;
                }
             mx[i][j] = max(dp[i][j] , mx[i][t]);
             t=j;
            }
        }
//     cout<<"Mx :\n";
//     for (int i=0;n>=i;i++) {
//         for (int j=0;n>=j;j++) {
//             cout<<(mx[i][j] == -INF?-1:mx[i][j])<<' ';
//            }
//         cout<<endl;
//        }
//     cout<<endl;
//     ans=-INF;
     for (int i=0;n>=i;i++) {
         for (int j=0;n>=j;j++) {
//             cout<<(dp[i][j] == -INF?-1:dp[i][j])<<' ';
             ans = max(ans,dp[i][j]);
            }
//         cout<<endl;
        }
     printf("%lld\n",ans);
    }
}