結果
問題 | No.15 カタログショッピング |
ユーザー | scache |
提出日時 | 2014-11-12 03:43:58 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 373 ms / 5,000 ms |
コード長 | 2,236 bytes |
コンパイル時間 | 3,933 ms |
コンパイル使用メモリ | 76,432 KB |
実行使用メモリ | 63,668 KB |
最終ジャッジ日時 | 2023-08-30 03:16:21 |
合計ジャッジ時間 | 6,901 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 123 ms
55,948 KB |
testcase_01 | AC | 140 ms
55,484 KB |
testcase_02 | AC | 145 ms
56,040 KB |
testcase_03 | AC | 149 ms
56,084 KB |
testcase_04 | AC | 144 ms
56,076 KB |
testcase_05 | AC | 317 ms
62,832 KB |
testcase_06 | AC | 346 ms
63,452 KB |
testcase_07 | AC | 373 ms
63,388 KB |
testcase_08 | AC | 356 ms
63,480 KB |
testcase_09 | AC | 358 ms
63,668 KB |
ソースコード
import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; /** * * @author scache * */ public class CatalogShopping { public static void main(String[] args) { CatalogShopping p = new CatalogShopping(); } public CatalogShopping() { 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){ boolean isFirst = true; for(int i=p.length-1;0<=i;i--){ if(((used>>i)&1)==1){ if(isFirst){ System.out.print(p.length-i); isFirst= false; }else{ 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; } } }