SRM539 Div1 Easy - Over9000Rocks

問題

石を無限に持っていて、9001個以上の石を箱に詰めたい
n個の箱があり、i番目の箱にはx[i]個以上y[i]個以下の石を詰めることができる
詰める石の個数が何通りあり得るか求めよ

1 <= n <= 15
1 <= x[i], y[i] <= 10^6

解法

2^15通り全列挙して使う箱の組み合わせを全部試す
使うと決めた箱たちのΣx[i]をsl、Σy[i]をsrとすると、詰める石の総数として有効な範囲は[max(sl,9001),sr]となる
この左端と右端のペアをvectorに突っ込んでソートしてマージしていけば良い

実装

最後マージするところのrは「答えに加算した範囲の右端」って意味

class Over9000Rocks {
public:
	int countPossibilities(vector<int> x, vector<int> y) {
		int n = x.size();
		vector<pair<int,int> > p;
		rep(i,1<<n) {
			int l = 0, r = 0;
			rep(j,n) if (i>>j&1) l += x[j], r += y[j];
			if (9000<r) p.push_back({max(l,9001), r});
		}
		sort(all(p));
		int res = 0, r = 0;
		each(i,p) if (r<i.second) {
			res += i.second - max(r+1, i.first) + 1;
			chmax(r, i.second);
		}
		return res;
	}
};