結果

問題 No.15 カタログショッピング
ユーザー opqopq_
提出日時 2015-05-14 17:22:01
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 80 ms / 5,000 ms
コード長 1,208 bytes
コンパイル時間 870 ms
コンパイル使用メモリ 70,596 KB
実行使用メモリ 18,028 KB
最終ジャッジ日時 2024-07-06 03:42:28
合計ジャッジ時間 1,639 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:12:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   12 |         scanf("%d%d", &N, &S);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp:13:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   13 |         for (int i = 0; i < N; i++) scanf("%d", P + i);
      |                                     ~~~~~^~~~~~~~~~~~~

ソースコード

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