POH_Light_Java

kirishima.java

import java.util.Arrays;

public class Main {
	// static-OJISAN!!
	static final int SIZE=8*(12+16*50);
	static byte[] buf=new byte[SIZE];
	static int count=0;
	static int answer = Integer.MAX_VALUE;
	static int m,n;
	static qclass q[];

	static class qclass implements Comparable {
		Float tanka;
		Integer ninzu;
		Integer kingaku;
		public int compareTo(Object obj) {
			qclass operand = (qclass) obj;
			if (this.tanka < operand.tanka) {
				return -1;
			} else if (this.tanka > operand.tanka) {
				return 1;
			} else {
				return 0;
			}
		}
	}

	static int read_int(){
		int r=0;
		while('\n'!=buf[count] && ' '!=buf[count] && '\0'!=buf[count] ){
			r = r * 10 + buf[count++] - '0';
		}
		count++;
		return r;
	}

	static void getMinCost(int index, int sumq, int sumr) {
		if (sumq >= m){
			if (sumr < answer){
				answer = sumr;
			}
		}
		else {
			if (index >= n){
			}
			else {
				int least_q = m - sumq;
				float least_r = sumr;
				int next_index = index + 1;
				for (int i=next_index;i<n;i++){
					if (q[i].ninzu < least_q){
					 	least_q = least_q - q[i].ninzu;
					 	least_r = least_r + q[i].kingaku;
					}
				}
				if (least_r >= answer){
				}
				else{
					getMinCost(next_index, sumq + q[index].ninzu, sumr + q[index].kingaku);
					getMinCost(next_index, sumq , sumr);
				}
			}
		}
	}

	public static void main(String[] args){
		try{
			// long start = System.currentTimeMillis();
			// long stop;
			int buf_size = System.in.read(buf,0,SIZE);

			// stop = System.currentTimeMillis();
			// System.out.println("!!!INPUT_TIME->" + (stop - start));

			// 1 ≦ m ≦ 200000
			m = read_int();

			// 1 ≦ n ≦ 50
			n = read_int();

			q = new qclass[n];

			// 1 ≦ q_i ≦ 10000
			// 1 ≦ r_i ≦ 5000000
			for (int i=0;i<n;i++){
				q[i] = new qclass();
				q[i].ninzu = read_int();
				q[i].kingaku = read_int();
				q[i].tanka = (float)q[i].kingaku / q[i].ninzu;
			}

			Arrays.sort(q);

			// for (int i=0;i<n;i++){
			// 	System.out.println("tanka->" + q[i].tanka + " ninzu->" + q[i].ninzu + " kingaku->" + q[i].kingaku);
			// }

			getMinCost(0,0,0);
			// System.out.println(answer);
			int oi = 0;
			int shou;
			int flg = 0;
			if (10000000 <= answer){
				shou = answer / 10000000;
				answer = answer % 10000000;
				buf[oi++] = (byte)('0' + shou);
				flg = 1;
			}
			if (1000000 <= answer){
				shou = answer / 1000000;
				answer = answer % 1000000;
				buf[oi++] = (byte)('0' + shou);
				flg = 1;
			}
			else {
				if (flg == 1){
					buf[oi++] = (byte)('0');
				}
			}
			if (100000 <= answer){
				shou = answer / 100000;
				answer = answer % 100000;
				buf[oi++] = (byte)('0' + shou);
				flg = 1;
			}
			else {
				if (flg == 1){
					buf[oi++] = (byte)('0');
				}
			}
			if (10000 <= answer){
				shou = answer / 10000;
				answer = answer % 10000;
				buf[oi++] = (byte)('0' + shou);
				flg = 1;
			}
			else {
				if (flg == 1){
					buf[oi++] = (byte)('0');
				}
			}
			if (1000 <= answer){
				shou = answer / 1000;
				answer = answer % 1000;
				buf[oi++] = (byte)('0' + shou);
				flg = 1;
			}
			else {
				if (flg == 1){
					buf[oi++] = (byte)('0');
				}
			}
			if (100 <= answer){
				shou = answer / 100;
				answer = answer % 100;
				buf[oi++] = (byte)('0' + shou);
				flg = 1;
			}
			else {
				if (flg == 1){
					buf[oi++] = (byte)('0');
				}
			}
			if (10 <= answer){
				shou = answer / 10;
				answer = answer % 10;
				buf[oi++] = (byte)('0' + shou);
				flg = 1;
			}
			else {
				if (flg == 1){
					buf[oi++] = (byte)('0');
				}
			}
			buf[oi++] = (byte)('0' + answer);
			buf[oi++] = 10;

			System.out.write(buf,0,oi);

			// stop = System.currentTimeMillis();
			// System.out.println("!!!TOTAL_TIME->" + (stop - start));
		}catch(Exception e){
			System.err.println(e);
		}
	}
}