Submission #00031

ソースコード

#include<bits/stdc++.h>
using namespace std;
 
int n,t,s;
int A[3010],B[3010];
int dp[3010][3010];
 
int solve(int cnt,int now){
  if(cnt == n || now > t) return 0;
  if(dp[cnt][now] != -1) return dp[cnt][now];
  int ret = 0;
  if(now < s && now+B[cnt] > s) {
    if(s+B[cnt] <= t) ret = max(ret,solve(cnt+1,s+B[cnt])+A[cnt]);
  }
  else {
    if(now+B[cnt] <= t) ret = max(ret,solve(cnt+1,now+B[cnt])+A[cnt]);
  }
  ret = max(ret,solve(cnt+1,now));
  return dp[cnt][now] = ret;
}
 
 
int main(){
  cin >> n >> t >> s;
  for(int i=0;i<n;i++){
    cin >> A[i] >> B[i];
  }
  memset(dp,-1,sizeof(dp));
  cout << solve(0,0) << endl;
}

ステータス

項目	データ
問題	0003 - 夜店 (Night Market)
ユーザー名	ei1428
投稿日時	2015-12-22 15:11:10
言語	C++11
状態	Accepted
得点	100
ソースコード長	660 Byte
最大実行時間	114 ms
最大メモリ使用量	36236 KB

セット

	セット	得点	Cases
1	Subtask1	10 / 10	01-*
2	Subtask2	10 / 10	02-*
3	Subtask3	10 / 10	03-*
4	Subtask4	10 / 10	04-*
5	Subtask5	10 / 10	05-*
6	Subtask6	10 / 10	06-*
7	Subtask7	10 / 10	07-*
8	Subtask8	10 / 10	08-*
9	Subtask9	10 / 10	09-*
10	Subtask10	10 / 10	10-*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
01-01.txt	AC	23 ms	35804 KB	1
01-02.txt	AC	21 ms	35704 KB	1
02-01.txt	AC	113 ms	35864 KB		2
02-02.txt	AC	106 ms	35876 KB		2
03-01.txt	AC	110 ms	36020 KB			3
03-02.txt	AC	114 ms	36160 KB			3
04-01.txt	AC	91 ms	36168 KB				4
04-02.txt	AC	86 ms	36184 KB				4
05-01.txt	AC	107 ms	36192 KB					5
05-02.txt	AC	102 ms	36204 KB					5
06-01.txt	AC	98 ms	36224 KB						6
06-02.txt	AC	95 ms	36236 KB						6
07-01.txt	AC	108 ms	36120 KB							7
07-02.txt	AC	106 ms	36136 KB							7
08-01.txt	AC	98 ms	36152 KB								8
08-02.txt	AC	101 ms	36164 KB								8
09-01.txt	AC	99 ms	36176 KB									9
09-02.txt	AC	114 ms	36188 KB									9
10-01.txt	AC	109 ms	36200 KB										10
10-02.txt	AC	110 ms	36216 KB										10