Submission #8478059


Source Code Expand

Copy
#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

Submission Time
Task E - All-you-can-eat
User tkmtSo
Language C++14 (GCC 5.4.1)
Score 0
Code Size 692 Byte
Status WA
Exec Time 26 ms
Memory 35584 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 4
AC × 14
WA × 17
Set Name Test Cases
Sample sample_01, sample_02, sample_03, sample_04
All corner_01, corner_02, corner_03, corner_04, corner_05, corner_06, corner_07, hand_01, hand_02, max_01, max_02, max_03, max_04, max_05, max_06, max_07, max_08, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
corner_01 AC 11 ms 35456 KB
corner_02 AC 12 ms 35456 KB
corner_03 AC 14 ms 35456 KB
corner_04 AC 11 ms 35456 KB
corner_05 AC 11 ms 35456 KB
corner_06 AC 11 ms 35456 KB
corner_07 WA 13 ms 35456 KB
hand_01 AC 10 ms 35456 KB
hand_02 AC 10 ms 35456 KB
max_01 WA 22 ms 35456 KB
max_02 WA 22 ms 35456 KB
max_03 AC 18 ms 35456 KB
max_04 AC 18 ms 35456 KB
max_05 WA 26 ms 35456 KB
max_06 WA 26 ms 35456 KB
max_07 WA 26 ms 35456 KB
max_08 WA 26 ms 35456 KB
random_01 WA 13 ms 35456 KB
random_02 WA 12 ms 35456 KB
random_03 WA 14 ms 35456 KB
random_04 WA 11 ms 35456 KB
random_05 WA 12 ms 35456 KB
random_06 WA 16 ms 35456 KB
random_07 WA 16 ms 35456 KB
random_08 WA 11 ms 35456 KB
random_09 WA 14 ms 35456 KB
random_10 WA 15 ms 35456 KB
sample_01 AC 10 ms 35456 KB
sample_02 AC 10 ms 35584 KB
sample_03 AC 10 ms 35456 KB
sample_04 AC 10 ms 35456 KB