結果

問題 No.15 カタログショッピング
コンテスト
ユーザー kenken714
提出日時 2019-04-19 00:24:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 23 ms / 5,000 ms
コード長 1,602 bytes
コンパイル時間 1,174 ms
コンパイル使用メモリ 101,916 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 10:49:25
合計ジャッジ時間 1,839 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>


ll n, sum, s[40];
vector<P> a, b;
vector<vector<ll>>ans;
int main() {
	cin >> n >> sum;
	ll h = n / 2;
	REP(i, n)cin >> s[i];
	REP(i, 1 << h) {
		ll now = 0;
		REP(j, h) {
			if (i & (1ll << j))now += s[j];
		}
		if (sum >= now)a.push_back(P(now, i));
	}
	REP(i, 1 << (n - h)) {
		ll now = 0;
		REP(j, (n - h)) {
			if (i & (1ll << j))now += s[h + j];
		}
		if (sum >= now)b.push_back(P(now, i));
	}
	sort(ALL(b));
	vector<ll> c;
	REP(i, b.size())c.push_back(b[i].first);
	REP(i, a.size()) {
		auto i1 = lower_bound(ALL(c), sum - a[i].first);
		auto i2 = lower_bound(ALL(c), sum - a[i].first + 1);
		FOR(j, i1 - c.begin(), i2 - c.begin()) {
			vector<ll> now;
			REP(k, h) {
				if (a[i].second & (1ll << k))now.push_back(k + 1);
			}
			REP(k, (n - h)) {
				if (b[j].second & (1ll << k))now.push_back(h + k + 1);
			}
			ans.push_back(now);
		}
	}
	sort(ALL(ans));
	REP(i, ans.size()) {
		REP(j, ans[i].size()) {
			if (j != 0)cout << " ";
			cout << ans[i][j];
		}
		cout << endl;
	}
}
0