結果
問題 | No.15 カタログショッピング |
ユーザー | ぴろず |
提出日時 | 2014-12-20 00:13:34 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 324 ms / 5,000 ms |
コード長 | 1,812 bytes |
コンパイル時間 | 4,119 ms |
コンパイル使用メモリ | 83,028 KB |
実行使用メモリ | 63,432 KB |
最終ジャッジ日時 | 2023-09-02 19:34:28 |
合計ジャッジ時間 | 6,272 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 124 ms
56,092 KB |
testcase_01 | AC | 125 ms
56,060 KB |
testcase_02 | AC | 128 ms
55,700 KB |
testcase_03 | AC | 127 ms
55,716 KB |
testcase_04 | AC | 125 ms
56,012 KB |
testcase_05 | AC | 291 ms
62,336 KB |
testcase_06 | AC | 309 ms
63,432 KB |
testcase_07 | AC | 304 ms
63,080 KB |
testcase_08 | AC | 324 ms
63,208 KB |
testcase_09 | AC | 301 ms
62,640 KB |
ソースコード
package no015; import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main { public static void main(String[] args) { 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(); } ArrayList<Pair> g1 = new ArrayList<>(); ArrayList<Pair> g2 = new ArrayList<>(); int n1 = n/2; int n2 = n - n1; for(int i=0;i<1<<n1;i++) { int sum = 0; for(int j=0;j<n1;j++) { if ((i>>j&1) == 1) { sum += p[n1-1-j]; } } g1.add(new Pair(sum,(long) i<<n2)); } for(int i=0;i<1<<n2;i++) { int sum = 0; for(int j=0;j<n2;j++) { if ((i>>j&1) == 1) { sum += p[n-1-j]; } } g2.add(new Pair(sum,i)); } Collections.sort(g1); Collections.sort(g2); ArrayList<Long> ans = new ArrayList<>(); int j = (1<<n2)-1; for(int i=0;i<1<<n1;i++) { while(j >= 0 && g1.get(i).sum + g2.get(j).sum > s) { j--; } int j2 = j; while(j >= 0 && g1.get(i).sum + g2.get(j).sum == s) { ans.add(g1.get(i).i + g2.get(j).i); j--; } j = j2; } Collections.sort(ans,Collections.reverseOrder()); for(long l:ans) { ArrayList<Integer> items = new ArrayList<>(); for(int i=0;i<n;i++) { if ((l>>i&1)==1) { items.add(n-1-i); } } Collections.reverse(items); StringBuilder sb = new StringBuilder(); for(int i=0;i<items.size();i++) { if (i >= 1) { sb.append(' '); } sb.append(items.get(i) + 1); } System.out.println(sb.toString()); } } static class Pair implements Comparable<Pair>{ long i; int sum; public Pair(int sum,long i) { this.sum = sum; this.i = i; } @Override public int compareTo(Pair o) { return Integer.compare(sum, o.sum); } } }