Submission #21941

ソースコード

?
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,t;
int v[1001];
int w[1001];
int mem[101][10001];
int dp(int i,int p);
int main(){
memset(mem,-1,sizeof(mem));
cin >> n >> t;
for(int i=0;i<n;i++){
cin >> v[i] >> w[i];
}
cout << dp(0,t) << endl;
return (0);
}
int dp(int i,int p){
if(mem[i][p] != -1) return mem[i][p];
if(i == n) return (0);
int res;
if(p >= w[i]){
res = max(dp(i+1,p),dp(i+1,p-w[i])+v[i]);
} else {
res=dp(i+1,p);
}
return mem[i][p]=res;
}

ステータス

項目 データ
問題 0238 - ナップザック問題(Easy)
ユーザー名 Artemis
投稿日時 2017-07-18 18:05:01
言語 C++11
状態 Accepted
得点 3
ソースコード長 575 Byte
最大実行時間 21 ms
最大メモリ使用量 4664 KB

セット

セット 得点 Cases
1 ALL 3 / 3 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
DPL_1_B_in1.txt AC 16 ms 4444 KB
1
DPL_1_B_in2.txt AC 16 ms 4584 KB
1
DPL_1_B_in3.txt AC 17 ms 4480 KB
1
DPL_1_B_in4.txt AC 18 ms 4544 KB
1
DPL_1_B_in5.txt AC 17 ms 4536 KB
1
DPL_1_B_in6.txt AC 14 ms 4528 KB
1
DPL_1_B_in7.txt AC 15 ms 4520 KB
1
DPL_1_B_in8.txt AC 13 ms 4512 KB
1
DPL_1_B_in9.txt AC 15 ms 4636 KB
1
DPL_1_B_in10.txt AC 11 ms 4436 KB
1
DPL_1_B_in11.txt AC 14 ms 4428 KB
1
DPL_1_B_in12.txt AC 15 ms 4412 KB
1
DPL_1_B_in13.txt AC 20 ms 4404 KB
1
DPL_1_B_in14.txt AC 13 ms 4396 KB
1
DPL_1_B_in15.txt AC 13 ms 4384 KB
1
DPL_1_B_in16.txt AC 12 ms 4376 KB
1
DPL_1_B_in17.txt AC 11 ms 4364 KB
1
DPL_1_B_in18.txt AC 16 ms 4480 KB
1
DPL_1_B_in19.txt AC 15 ms 4468 KB
1
DPL_1_B_in20.txt AC 19 ms 4448 KB
1
DPL_1_B_in21.txt AC 18 ms 4568 KB
1
DPL_1_B_in22.txt AC 14 ms 4560 KB
1
DPL_1_B_in23.txt AC 17 ms 4548 KB
1
DPL_1_B_in24.txt AC 16 ms 4664 KB
1
DPL_1_B_in25.txt AC 13 ms 4528 KB
1
DPL_1_B_in26.txt AC 13 ms 4520 KB
1
DPL_1_B_in27.txt AC 14 ms 4380 KB
1
DPL_1_B_in28.txt AC 16 ms 4500 KB
1
DPL_1_B_in29.txt AC 17 ms 4488 KB
1
DPL_1_B_in30.txt AC 19 ms 4604 KB
1
DPL_1_B_in31.txt AC 21 ms 4596 KB
1
DPL_1_B_in32.txt AC 18 ms 4588 KB
1
DPL_1_B_in33.txt AC 17 ms 4580 KB
1
DPL_1_B_in34.txt AC 14 ms 4568 KB
1
DPL_1_B_in35.txt AC 15 ms 4560 KB
1
DPL_1_B_in36.txt AC 16 ms 4424 KB
1