結果

問題 No.15 カタログショッピング
ユーザー hotpepsihotpepsi
提出日時 2015-03-23 00:08:36
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 40 ms / 5,000 ms
コード長 1,284 bytes
コンパイル時間 1,044 ms
コンパイル使用メモリ 89,072 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-06-29 00:17:41
合計ジャッジ時間 1,753 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 38 ms
10,624 KB
testcase_06 AC 38 ms
10,624 KB
testcase_07 AC 40 ms
10,624 KB
testcase_08 AC 39 ms
10,624 KB
testcase_09 AC 39 ms
10,624 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <sstream>
#include <vector>
#include <map>

using namespace std;

typedef long long LL;
typedef vector<LL> LLVec;
typedef map<LL, LLVec> LLMap;

int main(int argc, char *argv[])
{
	LL N, S;
	string s;
	{
		getline(cin, s);
		stringstream ss(s);
		ss >> N >> S;
	}
	LLVec P(N);
	for (LL i = 0; i < N; ++i) {
		getline(cin, s);
		stringstream ss(s);
		ss >> P[i];
	}
	LLMap m;
	LL a = N - N / 2;
	LL b = 1LL << a;
	for (LL c = 0; c < b; ++c) {
		LL p = 0;
		for (LL i = 0; i < a; ++i) {
			if ((1LL << i) & c) {
				p += P[N / 2 + i];
			}
		}
		if (p <= S) {
			m[p].push_back(c);
		}
	}
	vector<LLVec> ans;
	a = N / 2;
	b = 1LL << a;
	for (LL c = 0; c < b; ++c) {
		LL p = 0;
		for (LL i = 0; i < a; ++i) {
			if ((1LL << i) & c) {
				p += P[i];
			}
		}
		if (p <= S) {
			LLMap::const_iterator it = m.find(S - p);
			if (it != m.end()) {
				for (auto f : it->second) {
					LL x = c | (f << (N / 2));
					LLVec v;
					for (LL i = 0; i < N; ++i) {
						if ((1LL << i) & x) {
							v.push_back(i + 1);
						}
					}
					ans.push_back(v);
				}
			}
		}
	}
	sort(ans.begin(), ans.end());
	for (auto v : ans) {
		string delim = "";
		for (auto n : v) {
			cout << delim << n;
			delim = " ";
		}
		cout << endl;
	}
	return 0;
}
0