Submission #513157

---

Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Main {
	public static void main(String[] args) {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in),1);
		String[]s=getLine(r).split(" ");
		int N=Integer.parseInt(s[0]);
		int T=Integer.parseInt(s[1]);
		
		int[]A=new int[N],B=new int[N];
		int x=0,y=0;
		for(int i=0;i<N;i++){
			s=getLine(r).split(" ");
			A[i]=Integer.parseInt(s[0]);
			B[i]=Integer.parseInt(s[1]);
			x+=A[i];
			y+=B[i];
		}
		
		if(x<=T){
			System.out.println(0);
		}else if(y>T){
			System.out.println(-1);
		}else if(y==T){
			System.out.println(N);
		}else {
			HashMap<Integer,Integer>xx=new HashMap<Integer,Integer>();
			System.out.println(rec(A,B,N,T,0,0,0,xx));
		}
		
		
		
		
	}
	//num=配列番号、rec=Bの数
	static int rec(int[]A,int[]B,int N,int T,int time,int num,int rec,HashMap<Integer,Integer>list){
		if(N==num){
			return rec;
		}
		else if(list.containsKey(num*T+time)){
			return list.get(num*T+time);
		}
		
		int x=Integer.MAX_VALUE,y=Integer.MAX_VALUE;
		if(T>=time+A[num])
			x=rec(A,B,N,T,time+A[num],num+1,rec,list);//A+
		if(T>=time+B[num])
			y=rec(A,B,N,T,time+B[num],num+1,rec+1,list);//B
		
		int min=Math.min(x, y);
		if(list.containsKey(num*T+time)){
			if(min<list.get(num*T+time)){
				list.put(num*T+time, min);
			}
		}else {
			list.put(num*T+time, min);
		}
		return min;
	}
	
	static String getLine(BufferedReader r){
		try {
			return r.readLine();
		} catch (IOException e) {
			// TODO 自動生成された catch ブロック
			e.printStackTrace();
		}
		return null;
	}
	
}

Submission Info

Judge Result