AtCoder ABC #184 : F - Programming Contest

500ptならともかく600ptでこれが出るか。
https://atcoder.jp/contests/abc184/tasks/abc184_f

問題

N個の正整数が与えられる。
これらの部分集合の和のうち、Tを超えない範囲で最大値を求めよ。

解法

Nが最大40なので半分全列挙する。

int N;
ll T;
int A[51];
vector<ll> B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,40) cin>>A[i];
	int mask;
	FOR(mask,1<<20) {
		ll sum=0;
		FOR(i,20) if(mask&(1<<i)) sum+=A[20+i];
		if(sum<=T) B.push_back(sum);
	}
	sort(ALL(B));
	ll ret=0;
	FOR(mask,1<<20) {
		ll sum=0;
		FOR(i,20) if(mask&(1<<i)) sum+=A[i];
		if(sum<=T) {
			x=lower_bound(ALL(B),T-sum+1)-B.begin();
			if(x) ret=max(ret,sum+B[x-1]);
		}
	}
	cout<<ret<<endl;
}

まとめ

うーん。