結果

問題 No.15 カタログショッピング
ユーザー fura
提出日時 2020-01-03 13:57:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 23 ms / 5,000 ms
コード長 963 bytes
コンパイル時間 2,289 ms
コンパイル使用メモリ 186,424 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-22 19:09:17
合計ジャッジ時間 2,876 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;
using lint=long long;

int main(){
	int n;
	lint W; scanf("%d%lld",&n,&W);
	vector<int> w(n);
	rep(i,n) scanf("%d",&w[i]);

	vector<pair<lint,int>> Sum(1<<(n+1)/2);
	rep(S,1<<(n+1)/2){
		lint sum=0;
		rep(i,(n+1)/2) if(S>>i&1) sum+=w[n/2+i];
		Sum[S]={sum,S};
	}
	sort(Sum.begin(),Sum.end());

	vector<vector<int>> Ans;
	rep(S,1<<n/2){
		lint sum=0;
		rep(i,n/2) if(S>>i&1) sum+=w[i];
		if(sum>W) continue;

		auto it1=lower_bound(Sum.begin(),Sum.end(),make_pair(W-sum,0));
		auto it2=upper_bound(Sum.begin(),Sum.end(),make_pair(W-sum,1<<29));
		for(;it1!=it2;++it1){
			int T=it1->second;
			vector<int> res;
			rep(i,n/2) if(S>>i&1) res.emplace_back(i);
			rep(i,(n+1)/2) if(T>>i&1) res.emplace_back(n/2+i);
			Ans.emplace_back(res);
		}
	}

	sort(Ans.begin(),Ans.end());
	for(auto& ans:Ans) rep(i,ans.size()) printf("%d%c",ans[i]+1,i+1<ans.size()?' ':'\n');

	return 0;
}
0