結果

問題 No.15 カタログショッピング
ユーザー ゴリポン先生
提出日時 2025-05-31 16:50:11
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 1,058 bytes
コンパイル時間 5,671 ms
コンパイル使用メモリ 207,244 KB
実行使用メモリ 12,780 KB
最終ジャッジ日時 2025-05-31 16:50:23
合計ジャッジ時間 12,292 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// https://yang33-kassa.jp/yukicoder/yukicoder015/ より
import std;

void main()
{
	// 入力
	long N, S;
	readln.chomp.formattedRead("%d %d", N, S);
	auto A = new long[](N);
	foreach (ref a; A)
		a = readln.chomp.to!long;
	// 答えの計算(半分全列挙、ビットDP)
	alias P = Tuple!(long, long);
	P[] V;
	long n1 = N / 2;
	foreach (i; 0 .. 1L << n1) {
		long sum = 0, bit = 0;
		foreach (j; 0 .. n1) {
			if (i & (1L << j)) {
				sum += A[j];
				bit += 1L << (N - j);
			}
		}
		V ~= P(sum, bit);
	}
	V.sort;
	long n2 = N - n1;
	long[] ans;
	foreach (i; 0 .. 1L << n2) {
		long sum = 0, bit = 0;
		foreach (j; 0 .. n2) {
			if (i & (1 << j)) {
				sum += A[n1 + j];
				bit += 1L << (N - n1 - j);
			}
		}
		foreach (v; V.filter!(a => a[0] == S - sum)) {
			if (v[0] + sum == S)
				ans ~= v[1] | bit;
		}
	}
	// 答えの出力
	ans.sort!"a > b";
	foreach (a; ans) {
		bool ok = false;
		foreach (k; 0 .. N) {
			if (a & (1L << (N - k))) {
				if (ok) write(" ");
				ok = true;
				write(k + 1);
			}
		}
		if (ok) writeln();
	}
}
0