結果

問題 No.15 カタログショッピング
ユーザー ぴろず
提出日時 2014-12-20 00:13:34
言語 Java
(openjdk 23)
結果
AC  
実行時間 389 ms / 5,000 ms
コード長 1,812 bytes
コンパイル時間 3,122 ms
コンパイル使用メモリ 81,636 KB
実行使用メモリ 50,328 KB
最終ジャッジ日時 2024-06-12 01:58:24
合計ジャッジ時間 6,380 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

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);
		}
	}

}
0