結果
問題 | No.15 カタログショッピング |
ユーザー |
|
提出日時 | 2014-11-12 03:35:37 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 303 ms / 5,000 ms |
コード長 | 2,060 bytes |
コンパイル時間 | 2,443 ms |
コンパイル使用メモリ | 86,052 KB |
実行使用メモリ | 49,780 KB |
最終ジャッジ日時 | 2024-06-10 02:33:27 |
合計ジャッジ時間 | 5,324 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 127 ms
41,740 KB |
testcase_01 | AC | 114 ms
40,776 KB |
testcase_02 | AC | 136 ms
41,856 KB |
testcase_03 | AC | 128 ms
41,608 KB |
testcase_04 | AC | 125 ms
41,300 KB |
testcase_05 | AC | 247 ms
48,848 KB |
testcase_06 | AC | 278 ms
49,428 KB |
testcase_07 | AC | 303 ms
49,780 KB |
testcase_08 | AC | 289 ms
49,368 KB |
testcase_09 | AC | 291 ms
49,520 KB |
ソースコード
import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; /** * * @author scache * */ public class Main { public static void main(String[] args) { Main p = new Main(); } public Main() { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int s = sc.nextInt(); int[] p = new int[n]; for(int i=0;i<n;i++) p[i] = sc.nextInt(); solve(s, p); } ArrayList<ShoppingInfomation> list; public void solve(int s, int[] p) { list = new ArrayList<ShoppingInfomation>(); suf(s, p, p.length/2, 0, 0); Collections.sort(list); pre(s, p, 0, 0, 0); } private void pre(int s, int[] p, int n, int sum, int used){ if(sum>s) return; if(n==p.length/2){ int index = Collections.binarySearch(list, new ShoppingInfomation(s-sum, 0)); if(index<0) return ; for(int i=index;i>=0;i--){ if(list.get(i).price+sum==s) printResult(p, used+list.get(i).used); else break; } for(int i=index+1;i<list.size();i++){ if(list.get(i).price+sum==s) printResult(p, used+list.get(i).used); else break; } return; } pre(s, p, n+1, sum+p[n], used|(1<<(p.length-n-1))); pre(s, p, n+1, sum, used); } private void suf(int s, int[] p, int n, int sum, int used){ if(sum>s) return; if(n==p.length){ list.add(new ShoppingInfomation(sum, used)); return; } suf(s, p, n+1, sum+p[n], used|(1<<(p.length-n-1))); suf(s, p, n+1, sum, used); } private void printResult(int[] p, int used){ for(int i=p.length-1;0<=i;i--){ if(((used>>i)&1)==1){ System.out.print(p.length-i +" "); } } System.out.println(""); } private class ShoppingInfomation implements Comparable<ShoppingInfomation>{ int price; int used; public ShoppingInfomation(int price, int used){ this.price = price; this.used = used; } @Override public int compareTo(ShoppingInfomation o) { return price-o.price; } } }