Submission #28746

ソースコード

?
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
41
42
43
44
45
import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;
import java.util.function.Supplier;
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);
fill(bdp,BitSet::new);
dp[0]=0;
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(" "))
);
}
}
static <T> void fill(T[]t,Supplier<T>s){
for(int i=0;i<t.length;++i)
t[i]=s.get();
}
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
DPL_1_B_in1.txt AC 187 ms 15916 KB
1
DPL_1_B_in2.txt AC 106 ms 16020 KB
1
DPL_1_B_in3.txt AC 103 ms 16396 KB
1
DPL_1_B_in4.txt AC 107 ms 16448 KB
1
DPL_1_B_in5.txt AC 120 ms 16420 KB
1
DPL_1_B_in6.txt AC 109 ms 16516 KB
1
DPL_1_B_in7.txt AC 104 ms 18556 KB
1
DPL_1_B_in8.txt AC 108 ms 18076 KB
1
DPL_1_B_in9.txt AC 107 ms 17948 KB
1
DPL_1_B_in10.txt AC 105 ms 17964 KB
1
DPL_1_B_in11.txt AC 113 ms 18456 KB
1
DPL_1_B_in12.txt AC 109 ms 18028 KB
1
DPL_1_B_in13.txt AC 118 ms 18516 KB
1
DPL_1_B_in14.txt AC 115 ms 17956 KB
1
DPL_1_B_in15.txt AC 116 ms 18048 KB
1
DPL_1_B_in16.txt AC 120 ms 18020 KB
1
DPL_1_B_in17.txt AC 110 ms 16064 KB
1
DPL_1_B_in18.txt AC 111 ms 18256 KB
1
DPL_1_B_in19.txt AC 113 ms 16184 KB
1
DPL_1_B_in20.txt AC 111 ms 16516 KB
1
DPL_1_B_in21.txt AC 128 ms 17960 KB
1
DPL_1_B_in22.txt AC 122 ms 18448 KB
1
DPL_1_B_in23.txt AC 124 ms 18008 KB
1
DPL_1_B_in24.txt AC 131 ms 18356 KB
1
DPL_1_B_in25.txt AC 116 ms 18124 KB
1
DPL_1_B_in26.txt AC 117 ms 17972 KB
1
DPL_1_B_in27.txt AC 117 ms 18152 KB
1
DPL_1_B_in28.txt AC 116 ms 18508 KB
1
DPL_1_B_in29.txt AC 124 ms 18720 KB
1
DPL_1_B_in30.txt AC 126 ms 18036 KB
1
DPL_1_B_in31.txt AC 128 ms 18272 KB
1
DPL_1_B_in32.txt AC 123 ms 18476 KB
1
DPL_1_B_in33.txt AC 117 ms 18560 KB
1
DPL_1_B_in34.txt AC 126 ms 18124 KB
1
DPL_1_B_in35.txt AC 118 ms 18608 KB
1
DPL_1_B_in36.txt AC 118 ms 18300 KB
1