結果
問題 | No.50 おもちゃ箱 |
ユーザー |
![]() |
提出日時 | 2016-05-14 11:15:23 |
言語 | Java (openjdk 23) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,167 bytes |
コンパイル時間 | 3,085 ms |
コンパイル使用メモリ | 91,820 KB |
実行使用メモリ | 78,980 KB |
最終ジャッジ日時 | 2024-10-06 19:23:18 |
合計ジャッジ時間 | 12,636 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 WA * 2 |
ソースコード
import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.Scanner; public class Main { final static Integer DEL_VALUE = new Integer(99); public static void main(String[] args) { try (Scanner scan = new Scanner(System.in)) { int n = Integer.parseInt(scan.next()); ArrayList<Integer> a = new ArrayList<>(); for(int i=0; i<n; i++) { a.add(Integer.parseInt(scan.next())); } int m = Integer.parseInt(scan.next()); ArrayList<Integer> b = new ArrayList<>(); for(int i=0; i<m; i++) { b.add(Integer.parseInt(scan.next())); } a.sort(Collections.reverseOrder()); b.sort(Collections.reverseOrder()); LinkedList< ArrayList<Integer> > checkList = new LinkedList<>(); LinkedList< ArrayList<Integer> > nextCheckList = new LinkedList<>(); checkList.add(a); for(int i=0; i<b.size(); i++) { while(!checkList.isEmpty()) { final ArrayList<Integer> nowList = checkList.poll(); ArrayList<String> p = getPermutationList(b.get(i), nowList); for(String flag : p) { ArrayList<Integer> tmpList = (ArrayList<Integer>)nowList.clone(); for(int j=0; j<tmpList.size(); j++) { if(flag.charAt(j) == '1') { tmpList.set(j, DEL_VALUE); } } while( tmpList.indexOf(DEL_VALUE) >= 0 ) { tmpList.remove(DEL_VALUE); } if(tmpList.size() == 0) { System.out.println(i+1); System.exit(0); } nextCheckList.add(tmpList); } } checkList = (LinkedList< ArrayList<Integer> >)nextCheckList.clone(); nextCheckList.clear(); } System.out.println(-1); } } static ArrayList<String> getPermutationList(final int BOX_SIZE, ArrayList<Integer> a) { ArrayList<String> pList = new ArrayList<>(); int n = (int)Math.pow(2, a.size()); for(int i=n-1; i>=0; i--) { String flag = Integer.toBinaryString(i); int len = (a.size()-flag.length()); for(int j=0; j<len; j++) flag = "0" + flag; int sum = 0; for(int j=0; j<a.size(); j++) { if(flag.charAt(j) == '1') { sum += (a.get(j)); if(sum > BOX_SIZE) break; } } if(sum <= BOX_SIZE) { pList.add(flag); if(pList.size() >= 5) break; } } return pList; } }