Submission #1307414


Source Code Expand

import java.math.BigInteger;
import java.util.*;

public class Main {
	
	/*
	 * default function
	 * */	
	int ni() {
		return cin.nextInt();
	}
	
	long nl() {
		return cin.nextLong();
	}
	
	String line() {
		return cin.nextLine();
	}
	
	void println(String str) {	
		System.out.println(str);
	}
	
	void print(String str) {
		System.out.print(str);
	}
	
	/*
	 * default variable
	 */
	
	static final int MOD = 1000000007;
	
	Scanner cin = new Scanner(System.in);	
	String  output;
	
	public static void main(String[] args) {			
		new Main().run();						
	}
	
	/* default above */		
	public void run() {
			
		input();
		/* 
		 * start
		 */	
		
		solve();
		
		/*
		 * finish
		 */
		
		output = res + "";
		println(output);
			
	}
	/* 
	 * define variable
	 */
	
	int N, K;
	int[] nums;
	
	void input() {
		
		N = ni();
		K = ni();
		nums = new int[N];
		
		for (int i = 0; i < nums.length; i ++) {
			nums[i] = ni();
		}
	}
	
	
	int res;
	void solve() {
		
		Arrays.sort(nums);
		
		res = -1;
		
		int l = 0, r = N - 1;
		
		while (l <= r) {
			
			int mid = (l + r) / 2;
			
			
			if (judge(mid)) {
				r = mid - 1;
			} else {
				l = mid + 1;
				res = mid;
			}
		}
		
		res += 1;
		
	}
	
	boolean judge(int index) {
		
		if (nums[index] >= K) {
			return true;
		}
		
		BigInteger sum = BigInteger.ONE;
		
		for (int i = 0; i < N; i ++) {
			
			if (i == index) {
				continue;
			}
			
			sum = sum.or(sum.shiftLeft(nums[i]));
		}
		
		
		for (int i = K-1; i >= K - nums[index]; i --) {
			
			if (sum.testBit(i)) {
				return true;
			}
		}
		
		return false;
	}
	
}

Submission Info

Submission Time
Task D - No Need
User indcn20170030
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 1709 Byte
Status TLE
Exec Time 2114 ms
Memory 695380 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 0 / 300 0 / 300
Status
AC × 3
AC × 24
TLE × 1
MLE × 1
AC × 37
TLE × 13
MLE × 1
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
Subtask 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 2_026.txt, 2_027.txt, 2_028.txt, 2_029.txt, 2_030.txt, 2_031.txt, 2_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt, 2_041.txt, 2_042.txt, 2_043.txt, 2_044.txt, 2_045.txt, 2_046.txt, 2_047.txt, 2_048.txt, 2_049.txt, 2_050.txt
Case Name Status Exec Time Memory
0_000.txt AC 96 ms 21972 KB
0_001.txt AC 94 ms 17104 KB
0_002.txt AC 92 ms 19924 KB
1_003.txt AC 93 ms 21204 KB
1_004.txt AC 93 ms 20948 KB
1_005.txt AC 92 ms 21844 KB
1_006.txt AC 98 ms 20820 KB
1_007.txt AC 96 ms 19924 KB
1_008.txt AC 125 ms 21204 KB
1_009.txt AC 124 ms 23252 KB
1_010.txt AC 126 ms 19528 KB
1_011.txt AC 124 ms 22228 KB
1_012.txt AC 124 ms 19156 KB
1_013.txt AC 114 ms 21844 KB
1_014.txt AC 118 ms 18900 KB
1_015.txt AC 187 ms 39664 KB
1_016.txt AC 93 ms 19796 KB
1_017.txt AC 96 ms 20948 KB
1_018.txt AC 102 ms 18768 KB
1_019.txt AC 191 ms 36628 KB
1_020.txt AC 128 ms 22356 KB
1_021.txt AC 178 ms 31544 KB
1_022.txt TLE 2111 ms 676864 KB
1_023.txt MLE 1753 ms 695380 KB
1_024.txt AC 158 ms 30796 KB
1_025.txt AC 187 ms 33564 KB
2_026.txt AC 90 ms 21716 KB
2_027.txt AC 93 ms 19924 KB
2_028.txt AC 94 ms 20692 KB
2_029.txt AC 300 ms 39436 KB
2_030.txt AC 307 ms 43340 KB
2_031.txt AC 162 ms 26304 KB
2_032.txt AC 173 ms 25820 KB
2_033.txt AC 166 ms 26072 KB
2_034.txt AC 163 ms 25996 KB
2_035.txt AC 164 ms 28688 KB
2_036.txt TLE 2106 ms 348572 KB
2_037.txt AC 95 ms 19796 KB
2_038.txt AC 94 ms 20692 KB
2_039.txt AC 94 ms 21844 KB
2_040.txt TLE 2110 ms 348744 KB
2_041.txt TLE 2106 ms 228388 KB
2_042.txt TLE 2106 ms 229048 KB
2_043.txt TLE 2107 ms 549364 KB
2_044.txt TLE 2114 ms 629196 KB
2_045.txt TLE 2110 ms 411424 KB
2_046.txt TLE 2110 ms 349304 KB
2_047.txt TLE 2106 ms 345344 KB
2_048.txt TLE 2110 ms 230348 KB
2_049.txt TLE 2110 ms 364036 KB
2_050.txt TLE 2106 ms 352324 KB