Submission #00030

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
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;
/*
int ans = 0;
for(int i=0;i<n;i++){
ans = max(ans,solve(i,0));
}
cout << ans << endl;
*/
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01-01.txt AC 22 ms 35804 KB
1
01-02.txt AC 30 ms 35708 KB
1
02-01.txt TLE 1000 ms 35872 KB
2
02-02.txt TLE 1000 ms 35888 KB
2
03-01.txt TLE 1000 ms 35912 KB
3
03-02.txt TLE 1000 ms 35932 KB
3
04-01.txt TLE 1000 ms 35952 KB
4
04-02.txt TLE 1000 ms 35972 KB
4
05-01.txt TLE 1000 ms 35992 KB
5
05-02.txt TLE 1000 ms 36008 KB
5
06-01.txt TLE 1000 ms 36028 KB
6
06-02.txt TLE 1000 ms 36040 KB
6
07-01.txt TLE 1000 ms 36052 KB
7
07-02.txt TLE 1000 ms 36068 KB
7
08-01.txt TLE 1000 ms 36084 KB
8
08-02.txt TLE 1000 ms 36104 KB
8
09-01.txt TLE 1000 ms 36124 KB
9
09-02.txt TLE 1000 ms 36008 KB
9
10-01.txt TLE 1000 ms 36028 KB
10
10-02.txt TLE 1000 ms 36048 KB
10