PKU 1042 Gone Fishing

http://poj.org/problem?id=1042
n個の湖で釣りをする。
持ち時間はh時間あり、湖は1〜nまで順番に移動していく。(最後まで行かなくても可)
このとき、湖i〜i+1に移動するのにはti*5分かかり、湖iで釣り始めて最初の5分はfi匹釣ることが出来る。
5分釣り続けるごとに取れる魚がdi匹ずつ減っていく。
このとき、与えられた時間で魚を釣ることができる最大の匹数と、そのときの釣りの過程を表示しろというような問題。

dp+経路復元的な問題。
配列をdp[25][12*16]までしか確保していなくてめちゃくちゃWAりました。

int fi[25],di[25],ti[25],sti[25];

int dp[25][13*16];

main(){
  int n;
  bool nf=false;
  while(cin>>n,n){
    if(nf)cout<<endl;
    nf=true;
    int h;
    cin>>h;
    rep(i,n)cin>>fi[i];
    rep(i,n)cin>>di[i];
    rep(i,n-1){
      cin>>ti[i];
      sti[i+1]=sti[i]+ti[i];
    }

    memset(dp,0,sizeof(dp));
    int ans=0;

    rep(i,n){
      for(int st=sti[i];st<=h*12;++st){
        if(i)dp[i][st]=max(dp[i][st],dp[i-1][st-ti[i-1]]);
        int tp=fi[i];
        int sp=0;
        if(i)sp=dp[i-1][st-ti[i-1]];
        for(int et=st+1;et<=h*12;++et){
          dp[i][et]=max(dp[i][et],max(tp,0)+sp);
          sp+=max(tp,0);
          tp-=di[i];
        }
      }
    }
    rep(i,n)rep(j,h*12+1)ans=max(ans,dp[i][j]);
    
    vector<int>tim;
    rep(s,n){
      if(ans==dp[s][h*12]){
        int ct=h*12;
        rep(i,n-s-1)tim.pb(0);
        for(int ns=s-1;ns>=0;--ns){
          for(int nt=ct-ti[ns];nt>=0;--nt){
            int tp=0;
            for(int i=0;nt+i+ti[ns]<ct;++i)tp+=max(fi[ns+1]-di[ns+1]*i,0);
            if(dp[ns][nt]+tp==dp[ns+1][ct]){
              tim.pb(ct-nt-ti[ns]);
              ct=nt;
              break;
            }
          }
        }
        tim.pb(ct);
        break;
      }
    }

    while(SZ(tim)<n)tim.pb(0);
    reverse(ALL(tim));
    rep(i,SZ(tim)){
      if(i)cout<<", ";
      cout<<tim[i]*5;
    }
    cout<<endl;
    cout<<"Number of fish expected: "<<ans<<endl;
  }
}