SRM 539 250pt : Over9000Rocks

問題概要

N(≦16)個の箱があり、各箱の中には石が十分たくさん入っている。この箱の中からいくつか選び、lower[i]以上upper[i](1

解法

愚直に塗りつぶしたりsegtree使ったりしても解けるらしいけど、時間空間ともに危険域なので別の方針で頑張る。
部分集合を全列挙して下界の和と上界の和を選んで(9000, inf)との共通部分をとる。

acceptされたコード

#include <vector>
#include <algorithm>
using namespace std;

struct Over9000Rocks {

	int countPossibilities(vector <int> lowerBound, vector <int> upperBound) {
		const int N = lowerBound.size();
		vector<pair<int,int> > rs;
		for(int bit=0; bit<(1<<N); bit++){
			int lower = 0, upper = 0;
			for(int i=0; i<N; i++)if( (bit>>i)&1 ){
				lower += lowerBound[i];
				upper += upperBound[i];
			}
			if(upper > 9000){
				rs.push_back(make_pair(max(9001, lower), upper));
			}
		}
		sort(rs.begin(), rs.end());

		int ans = 0;
		int pl = 0, pu = 0;
		for(int i=0; i<(int)rs.size(); ++i){
			pl = max(pl, rs[i].first);
			pu = max(pu, rs[i].second);
			if(pl <= pu){
				ans += (pu - pl + 1);
			}
			pl = pu + 1;
		}

		return ans;
	}

};