Kick Start 2019 Round G Problem C shifts 两种解法（SOS DP， Segment tree)

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Solution{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
		int T = in.nextInt();	
		for(int cas = 1; cas <= T; cas++){
			int n = in.nextInt();
			int h = in.nextInt();
			long[] a = new long[n];
			long[] b = new long[n];
			long sumA = 0L;   long sumB = 0L;
			for(int i = 0; i < n; i++){
				a[i] = in.nextLong();
				sumA += a[i];
			}
			for(int i = 0; i < n; i++){
				b[i] = in.nextLong();
				sumB += b[i];
			}
			if(sumA < h || sumB < h){
				System.out.println("Case #"+cas+": "+0);
				continue;
			}
			
			ArrayList<Pair> list1 = new ArrayList<>();
			recur(a,b,0,n/2,0L,0L,list1,h);
			ArrayList<Pair> list2 = new ArrayList<>();
			recur(a,b,n/2+1,n-1,0L,0L,list2,h);
			Collections.sort(list1);
			Collections.sort(list2);
			SegTree tree = new SegTree(0,h);
			long ans = 0;			
			int p = list2.size() - 1;
			for(Pair pair: list1){
				while(p >= 0 && list2.get(p).fir >= h - pair.fir){
					tree.add(list2.get(p).sec);
					p--;
				}
				ans += tree.get(h - pair.sec, h);
			}
			System.out.println("Case #"+cas+": "+ans);				
		}
	}
	
	static class SegTree{
		int low, high;
		SegTree left, right;
		int sum = 0;
		public SegTree(int a, int b){
			low = a;  high = b;
		}
		public void add(int v){
			sum++;
			if(low == high)
				return;
			int m = low + (high-low)/2;
			if(v <= m){
				if(left == null)
					left = new SegTree(low,m);
				left.add(v);
			}
			else{
				if(right == null)
					right = new SegTree(m+1,high);
				right.add(v);
			}
		}

		public int get(int a, int b){
			if(a <= low && b >= high)
				return sum;
			if(a > high || b < low)
				return 0;
			int res = 0;
			if(left != null)
				res = left.get(a,b);
			if(right != null)
				res += right.get(a,b);
			return res;
		}
	}
	static class Pair implements Comparable<Pair>{
		int fir, sec;
		public Pair(int a, int b){
			fir = a;  sec = b;
		}
		public int compareTo(Pair pair){
			return Integer.compare(fir, pair.fir);
		}
	}

	static void recur(long[] a, long[] b, int p, int end, long accuA, long accuB, ArrayList<Pair> list,int h){
		if(p > end){
			list.add(new Pair((int)Math.min(h,accuA), (int)Math.min(h,accuB)));
			return;
		}
		recur(a,b,p+1,end,accuA+a[p],accuB,list,h);
		recur(a,b,p+1,end,accuA, accuB+b[p],list,h);
		recur(a,b,p+1,end,accuA+a[p],accuB+b[p],list,h);
	}
}