結果

問題 No.15 カタログショッピング
ユーザー nsd_fbnsd_fb
提出日時 2015-02-20 11:24:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 467 ms / 5,000 ms
コード長 1,163 bytes
コンパイル時間 2,739 ms
コンパイル使用メモリ 161,272 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-06 02:30:09
合計ジャッジ時間 4,376 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_N = 31;

int n, s;
pair<int, int> p[MAX_N];
int accumulation[MAX_N];

vector<vector<int>> ans;

void dfs(int index, int money, vector<int> &goods) {
	if(money == s) {
		vector<int> tmp(goods);
		sort(begin(tmp), end(tmp));
		ans.emplace_back(tmp);
		return;
	}

	if(index == n) return;

	const int next_money = money + p[index].first;
	if(next_money <= s) {
		goods.emplace_back(p[index].second);
		dfs(index + 1, next_money, goods);
		goods.pop_back();
	}

	if(money + accumulation[index] >= s) dfs(index + 1, money, goods);
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	
	cin >> n >> s;

	for(int i = 0; i < n; ++i) {
		int price;
		cin >> price;
		p[i] = make_pair(price, i + 1);
	}

	sort(p, p + n, greater<pair<int, int>>());

	for(int i = n - 2; i >= 0; --i) {
		accumulation[i] = accumulation[i + 1] + p[i + 1].first;
	}

	ans.reserve(n * n);
	vector<int> goods;
	dfs(0, 0, goods);

	sort(begin(ans), end(ans));
	for(const auto &vec : ans) {
		for(int i = 0; i < vec.size(); ++i) {
			cout << vec[i] << (i + 1 == vec.size() ? '\n' : ' ');
		}
	}

	return EXIT_SUCCESS;
}
0