結果

問題 No.15 カタログショッピング
ユーザー furafura
提出日時 2020-01-03 13:57:21
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 19 ms / 5,000 ms
コード長 963 bytes
コンパイル時間 2,094 ms
コンパイル使用メモリ 185,608 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-05-02 07:14:12
合計ジャッジ時間 2,353 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 16 ms
6,944 KB
testcase_06 AC 19 ms
6,940 KB
testcase_07 AC 19 ms
6,944 KB
testcase_08 AC 19 ms
6,940 KB
testcase_09 AC 19 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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