結果
問題 | No.393 2本の竹 |
ユーザー |
|
提出日時 | 2016-07-12 23:43:38 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 205 ms / 1,000 ms |
コード長 | 2,286 bytes |
コンパイル時間 | 4,581 ms |
コンパイル使用メモリ | 84,144 KB |
実行使用メモリ | 41,664 KB |
最終ジャッジ日時 | 2024-11-08 05:45:53 |
合計ジャッジ時間 | 7,058 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
import java.io.*;import java.util.*;public class Main_yukicoder393 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);Printer pr = new Printer(System.out);int d = sc.nextInt();for (int tcase = 0; tcase < d; tcase++) {int n1 = sc.nextInt();int n2 = sc.nextInt();int n = n1 + n2;n1 = Math.min(n1, n2);int m = sc.nextInt();int[] a = new int[m];for (int i = 0; i < m; i++) {a[i] = sc.nextInt();}Arrays.sort(a);int[] sum = new int[m + 1];for (int i = 1; i <= m; i++) {sum[i] = sum[i - 1] + a[i - 1];}int tmp = Arrays.binarySearch(sum, n);int ret = tmp >= 0 ? tmp : -(tmp + 1) - 1;int ok = n1 - (n - sum[ret]);BitSet bs = new BitSet(n1 + 1);bs.set(0);for (int i = 0; i < ret; i++) {for (int j = bs.length(); (j = bs.previousSetBit(j - 1)) >= 0; ) {if (j + a[i] > n1) {continue;} else {bs.set(j + a[i]);}}}if (bs.previousSetBit(bs.length() - 1) >= ok) {pr.println(ret);} else {pr.println(ret - 1);}}sc.close();pr.close();}@SuppressWarnings("unused")private static class Scanner {BufferedReader br;Iterator<String> it;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}String next() throws RuntimeException {try {if (it == null || !it.hasNext()) {it = Arrays.asList(br.readLine().split(" ")).iterator();}return it.next();} catch (IOException e) {throw new IllegalStateException();}}int nextInt() throws RuntimeException {return Integer.parseInt(next());}long nextLong() throws RuntimeException {return Long.parseLong(next());}float nextFloat() throws RuntimeException {return Float.parseFloat(next());}double nextDouble() throws RuntimeException {return Double.parseDouble(next());}void close() {try {br.close();} catch (IOException e) {// throw new IllegalStateException();}}}private static class Printer extends PrintWriter {Printer(PrintStream out) {super(out);}}}