結果

問題 No.15 カタログショッピング
ユーザー furafura
提出日時 2020-01-03 13:50:21
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 872 bytes
コンパイル時間 2,088 ms
コンパイル使用メモリ 177,116 KB
実行使用メモリ 5,432 KB
最終ジャッジ日時 2023-08-14 19:11:37
合計ジャッジ時間 2,825 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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.emplace_back(sum,S);
	}
	sort(Sum.begin(),Sum.end());

	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> ans;
			rep(i,n/2) if(S>>i&1) ans.emplace_back(i);
			rep(i,(n+1)/2) if(T>>i&1) ans.emplace_back(n/2+i);
			rep(i,ans.size()) printf("%d%c",ans[i]+1,i+1<ans.size()?' ':'\n');
		}
	}

	return 0;
}
0