Submission #133614

---

Source Code Expand

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
 
 
public class Main {
	
	int x;private int v =0;
	int counter=0;
	int previous = 0;
	Integer[] shohin;
	SortedMap<Integer,Integer> weightlist = new TreeMap<Integer, Integer>(
			new Comparator<Integer>() {

				@Override
				public int compare(Integer o1, Integer o2) {
					// TODO 自動生成されたメソッド・スタブ
					return o1-o2;
				}
	});
	
	public Main(int x,int n) {
	 this.x=x;
	 shohin = new Integer[n];
	 weightlist.put(Integer.valueOf(0),1);
	}
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();
		Main main = new Main(x,n/2);
		for(int i = 0; i<n/2;i++) main.add(sc.nextInt());
		Main main2 = new Main(x,n-n/2);
		for(int i = n/2; i<n;i++) main2.add(sc.nextInt());
		main.start();main2.start();
		int v=0;
		for(Integer i : main2.weightlist.keySet()){
			if(main.weightlist.containsKey(x-i)){
				v += main2.weightlist.get(i) * main.weightlist.get(x-i);
			}
		}
		System.out.println(main.getV()+main2.getV()+ v);
	}
 
	private void start() {
		Arrays.sort(shohin,Collections.reverseOrder());
		for(int value :shohin) add2(value);
	}
	
	private void add(int value){
		shohin[counter] = value;
		counter++;
	}
	
	private void add2(int value) {
		int t;
		SortedMap<Integer, Integer> karilist = new TreeMap<Integer, Integer>(weightlist);
		for(Integer	i: weightlist.keySet()){
			t=i+value;
			Integer k;
			if(t<x){
					karilist.put(
							Integer.valueOf(t),
							(k=weightlist.get(t))==null ? weightlist.get(i):k+weightlist.get(i)
								);
			}else if(t==x){
				v+=weightlist.get(i);
			}else break;
		}
		weightlist = karilist;
	}
 
	public int getV() {
		return v;
	}
 
	public void setV(int v) {
		this.v = v;
	}
	
	
	
}

Submission Info

Judge Result