Submission #28747

ソースコード

?
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
37
38
39
40
import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;
import java.util.stream.Collectors;
public class Main{
static Scanner s=new Scanner(System.in);
static int gInt() {return s.nextInt();}
public static void main(String[]$){
int n=gInt(),wlim=gInt();
int[]dp=new int[wlim+1];
BitSet[]bdp=new BitSet[wlim+1];
Arrays.fill(dp,-1145141919);
dp[0]=0;
Arrays.setAll(bdp,i->new BitSet());
for(int g=0;g<n;++g) {
int v=gInt(),w=gInt();
for(int i=wlim-w;i>=0;--i){
if(dp[i+w]<dp[i]+v) {
dp[i+w]=dp[i]+v;
bdp[i+w].clear();
bdp[i+w].or(bdp[i]);
bdp[i+w].set(g+1);
}
}
}
int resindex=0;
for(int i=1;i<=wlim;++i)
if(dp[resindex]<dp[i])
resindex=i;
System.out.println(dp[resindex]);
BitSet resbit=bdp[resindex];
if(!resbit.isEmpty()) {
System.out.println(
resbit.stream().mapToObj(String::valueOf)
.collect(Collectors.joining(" "))
);
}
}
}

ステータス

項目 データ
問題 0240 - ナップザック問題(Expert)
ユーザー名 fal_rnd
投稿日時 2017-11-17 01:13:50
言語 Java
状態 Accepted
得点 7
ソースコード長 983 Byte
最大実行時間 129 ms
最大メモリ使用量 18644 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
DPL_1_B_in1.txt AC 110 ms 16300 KB
1
DPL_1_B_in2.txt AC 123 ms 15924 KB
1
DPL_1_B_in3.txt AC 112 ms 16256 KB
1
DPL_1_B_in4.txt AC 108 ms 16308 KB
1
DPL_1_B_in5.txt AC 105 ms 16284 KB
1
DPL_1_B_in6.txt AC 116 ms 15984 KB
1
DPL_1_B_in7.txt AC 104 ms 16360 KB
1
DPL_1_B_in8.txt AC 114 ms 18384 KB
1
DPL_1_B_in9.txt AC 108 ms 18108 KB
1
DPL_1_B_in10.txt AC 111 ms 18188 KB
1
DPL_1_B_in11.txt AC 109 ms 18008 KB
1
DPL_1_B_in12.txt AC 109 ms 18508 KB
1
DPL_1_B_in13.txt AC 108 ms 18004 KB
1
DPL_1_B_in14.txt AC 115 ms 18376 KB
1
DPL_1_B_in15.txt AC 114 ms 18340 KB
1
DPL_1_B_in16.txt AC 123 ms 18172 KB
1
DPL_1_B_in17.txt AC 99 ms 16164 KB
1
DPL_1_B_in18.txt AC 114 ms 18012 KB
1
DPL_1_B_in19.txt AC 103 ms 15820 KB
1
DPL_1_B_in20.txt AC 106 ms 16288 KB
1
DPL_1_B_in21.txt AC 115 ms 17892 KB
1
DPL_1_B_in22.txt AC 126 ms 17876 KB
1
DPL_1_B_in23.txt AC 122 ms 17856 KB
1
DPL_1_B_in24.txt AC 126 ms 17800 KB
1
DPL_1_B_in25.txt AC 111 ms 18252 KB
1
DPL_1_B_in26.txt AC 110 ms 18188 KB
1
DPL_1_B_in27.txt AC 108 ms 18276 KB
1
DPL_1_B_in28.txt AC 118 ms 18228 KB
1
DPL_1_B_in29.txt AC 119 ms 17992 KB
1
DPL_1_B_in30.txt AC 120 ms 18644 KB
1
DPL_1_B_in31.txt AC 126 ms 18404 KB
1
DPL_1_B_in32.txt AC 127 ms 18228 KB
1
DPL_1_B_in33.txt AC 129 ms 18568 KB
1
DPL_1_B_in34.txt AC 117 ms 18068 KB
1
DPL_1_B_in35.txt AC 121 ms 18412 KB
1
DPL_1_B_in36.txt AC 124 ms 18128 KB
1