結果

問題 No.15 カタログショッピング
ユーザー opqopq_opqopq_
提出日時 2015-05-14 17:22:01
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 105 ms / 5,000 ms
コード長 1,208 bytes
コンパイル時間 1,096 ms
コンパイル使用メモリ 85,280 KB
実行使用メモリ 17,728 KB
最終ジャッジ日時 2023-09-20 07:49:17
合計ジャッジ時間 2,527 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 95 ms
17,720 KB
testcase_06 AC 102 ms
17,720 KB
testcase_07 AC 104 ms
17,724 KB
testcase_08 AC 105 ms
17,720 KB
testcase_09 AC 104 ms
17,728 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

#define N_MAX 31
int N, S;
int P[N_MAX];

int main() {
	scanf("%d%d", &N, &S);
	for (int i = 0; i < N; i++) scanf("%d", P + i);
	
	vector<pair<int, vector<int>>> v;
	for (int i = 1; i < 1 << N / 2; i++) {
		int sum = 0;
		vector<int> id;
		for (int j = 0; 1 << j <= i; j++) {
			if (i & 1 << j) {
				sum += P[j];
				id.push_back(j + 1);
			}
		}
		v.emplace_back(sum, id);
	}
	
	map<int, vector<vector<int>>> m;
	for (unsigned i = 1 << N / 2; i < 1LL << N; i += 1 << N / 2) {
		int sum = 0;
		vector<int> id;
		for (int j = N / 2; 1u << j <= i; j++) {
			if (i & 1u << j) {
				sum += P[j];
				id.push_back(j + 1);
			}
		}
		m[sum].push_back(id);
	}
	
	vector<vector<int>> res;
	for (auto& p : v) {
		if (p.first == S) {
			res.push_back(p.second);
			continue;
		}
		for (auto& _ : m[S - p.first]) {
			auto tmp = p.second;
			for (auto& e : _) tmp.push_back(e);
			res.push_back(tmp);
		}
	}
	for (auto& _ : m[S]) res.push_back(_);
	
	sort(res.begin(), res.end());
	
	for (auto& _ : res) {
		for (int i = 0; i < _.size(); i++) {
			printf("%d%c", _[i], i + 1 < _.size() ? ' ' : '\n');
		}
	}
	
	return 0;
}
0