JOI本選過去問 第11回 日本情報オリンピック本選 3問目 夜店

問題はこちら

なんかいろいろめんどくさかった。

• メモリに気をつけよう（節約しました

• 細かいとこばぐんないようにしよう。

• あとは気合

• ソースとても汚いけどまわりと比較して実行時間そこまで遅くないので吉としよう。

#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;

int n = 0;

int s = 0,t = 0;

int ans = 0;

int d[3003][2] = {0};

int dp[3003][3003] = {0};

int tmp[3003] = {0};

int main(){

  scanf("%d%d%d",&n,&t,&s);

  for(int i = 0;i < n;i++){
    scanf("%d%d",&d[i][0],&d[i][1]);
  }
  
  for(int i = 0;i < n;i++){
    for(int j = 0;j <= s;j++){
      if(j < d[i][1]){
	dp[i+1][j] = dp[i][j];
      }else{
	dp[i+1][j] = max(dp[i][j],dp[i][j-d[i][1]]+d[i][0]);
      }
    }
  }
  
  for(int i = 1;i <= n;i++){
    tmp[i] = dp[i][s];
  }

  memset(dp,0,sizeof(dp));

 
  for(int i = n-1;i >= 0;i--){
    for(int j = 0;j <= t - s;j++){
      if(j < d[i][1]){
	dp[i][j] = dp[i+1][j];
      }else{
	dp[i][j] = max(dp[i+1][j],dp[i+1][j-d[i][1]]+d[i][0]);
      }
    }
  }

  ans = dp[0][t-s];
  ans = max(tmp[n],ans);
  for(int i = 0;i < n;i++){
    ans = max(ans,tmp[i+1]+dp[i+1][t-s]);
  }

  printf("%d\n",ans);

}