Submission #1962247


Source Code Expand

import java.io.IOException;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) throws IOException {
		Main main = new Main();
		main.solveD();
	}

	private void solveD() throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] a = new int[N];
		for (int i = 0; i < N; i++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		int left = 0;
		int right;
		for (right = N - 1; right >= 0 && a[right] >= K; right--);
		right++;
		while (left < right) {
			int current = (left + right) / 2;
			if (judge(current, a, K)) {
				left = current + 1;
			} else {
				right = current;
			}
		}
		System.out.println(left);
	}

	private boolean judge(int current, int[] a, int K) {
		int N = a.length;
		Set<Integer> set = new HashSet<>(K * 4 / 3 + 1);
		set.add(0);
		for (int i = 0; i < N; i++) {
			if (current == i) {
				continue;
			}
			Set<Integer> newSet = new HashSet<>(K * 4 / 3 + 1);
			newSet.addAll(set);
			for (int num : set) {
				if (num + a[i] < K) {
					newSet.add(num + a[i]);
				}
			}
			set = newSet;
		}
		return set.stream().mapToInt(o -> o).filter(o -> (K - a[current] <= o)).count() == 0;
	}
}

Submission Info

Submission Time
Task D - No Need
User schwarzahl
Language Java8 (OpenJDK 1.8.0)
Score 300
Code Size 1331 Byte
Status TLE
Exec Time 2114 ms
Memory 346592 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 300 / 300 0 / 300
Status
AC × 3
AC × 26
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 204 ms 25156 KB
0_001.txt AC 182 ms 24660 KB
0_002.txt AC 183 ms 24772 KB
1_003.txt AC 95 ms 20816 KB
1_004.txt AC 97 ms 20560 KB
1_005.txt AC 97 ms 21204 KB
1_006.txt AC 198 ms 26580 KB
1_007.txt AC 204 ms 24784 KB
1_008.txt AC 364 ms 46328 KB
1_009.txt AC 356 ms 47128 KB
1_010.txt AC 130 ms 21324 KB
1_011.txt AC 125 ms 18900 KB
1_012.txt AC 126 ms 21968 KB
1_013.txt AC 125 ms 21460 KB
1_014.txt AC 117 ms 23508 KB
1_015.txt AC 458 ms 50112 KB
1_016.txt AC 190 ms 24784 KB
1_017.txt AC 208 ms 27220 KB
1_018.txt AC 180 ms 27092 KB
1_019.txt AC 268 ms 32340 KB
1_020.txt AC 229 ms 29264 KB
1_021.txt AC 322 ms 42628 KB
1_022.txt AC 262 ms 35348 KB
1_023.txt AC 215 ms 29396 KB
1_024.txt AC 321 ms 39920 KB
1_025.txt AC 314 ms 41900 KB
2_026.txt AC 94 ms 20052 KB
2_027.txt AC 212 ms 24528 KB
2_028.txt AC 214 ms 27084 KB
2_029.txt TLE 2111 ms 346592 KB
2_030.txt TLE 2114 ms 340424 KB
2_031.txt AC 170 ms 25484 KB
2_032.txt AC 173 ms 28976 KB
2_033.txt AC 169 ms 28208 KB
2_034.txt AC 164 ms 25148 KB
2_035.txt AC 170 ms 27512 KB
2_036.txt TLE 2114 ms 346156 KB
2_037.txt AC 211 ms 26576 KB
2_038.txt AC 229 ms 29236 KB
2_039.txt AC 211 ms 27220 KB
2_040.txt MLE 1548 ms 340116 KB
2_041.txt TLE 2114 ms 343904 KB
2_042.txt TLE 2114 ms 344384 KB
2_043.txt TLE 2114 ms 343064 KB
2_044.txt TLE 2114 ms 340832 KB
2_045.txt TLE 2114 ms 345964 KB
2_046.txt TLE 2114 ms 342208 KB
2_047.txt TLE 2114 ms 342516 KB
2_048.txt TLE 2114 ms 346344 KB
2_049.txt TLE 2114 ms 344288 KB
2_050.txt TLE 2114 ms 344296 KB