[Link] https://www.acmicpc.net/problem/1450
When N = 30 Time complexity is O(2^30) > O(10^9) In order to reduce time complexity, cut the baggage to half
which reduces time complexity to O(2^15 * O(log2(2^15)))
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br;
static int[] bag;
static int c;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int[] arr = getArr();
int n = arr[0];
c = arr[1];
ArrayList<Integer> leftList = new ArrayList<>();
ArrayList<Integer> rightList = new ArrayList<>();
bag = getArr();
int ans = 0;
dfs(leftList, 0, 0, (n - 1)/2);
dfs(rightList, 0, (n - 1)/2 + 1, n - 1);
ans = leftList.size() + rightList.size();
Collections.sort(leftList);
Collections.sort(rightList);
for(int i = 0; i < leftList.size(); i++) {
int index = binarySearch(rightList, c - leftList.get(i));
if(index != - 1) ans += index;
else break;
}
print(ans + 1);
}
static int binarySearch(ArrayList<Integer> al , int val) {
if(al.size() == 0) return -1;
int left = 0, right = al.size() - 1, mid, ans = -1;
if(val < al.get(0)) return -1;
while(left <= right) {
mid = (left + right) / 2;
if(al.get(mid) <= val) left = mid + 1;
else if(al.get(mid) > val) right = mid - 1;
}
return left;
}
static void dfs(ArrayList<Integer> al, int sum, int left, int right) {
if(sum > c) return;
if(left > right) {
if(sum != 0) al.add((int)sum);
return;
}
dfs(al, sum, left + 1, right);
dfs(al, sum + bag[left], left + 1, right);
}
static int toi(String s) { return Integer.parseInt(s); }
static String[] getLine() throws IOException { return br.readLine().split(" "); }
static int[] getArr() throws IOException { return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
static <T> void print(T s) { System.out.print(s); }
static <T> void println(T s) { System.out.println(s); }
}