Submission #8478059

---

Source Code Expand

#include <cmath>
#include <iostream>
#include <vector>

int main(){
  int N,T;
  std::cin >> N >> T;
  std::vector<int> A_arr(N), B_arr(N);
  for(int i = 0; i < N; i++){
    std::cin >> A_arr[i] >> B_arr[i];
  }

  int dp[3001][3001] = {};

  for(int i = 0; i < N; i++){
    int A = A_arr[i];
    int B = B_arr[i];
    for(int j = 0; j < T; j++){
      if(j < A){
        dp[i+1][j] = dp[i][j];
      }else{
        dp[i+1][j] = std::max(dp[i][j], B+dp[i][j-A]);
      }
    }
  }

  int tmax = dp[N][T-1];
  int bmax = 0;
  for(int i = N-1; i >= 0; i--){
    bmax = std::max(bmax, B_arr[i]);
    tmax = std::max(tmax, dp[i][T-1]+bmax);
  }

  std::cout << tmax << std::endl;

  return 0;
}

Submission Info

Judge Result