SRM539 Div1 Easy

250
区間の両端だけ記憶して、それをマージしていく。

class Over9000Rocks {
public:
  int countPossibilities(vector <int> L, vector <int> U)
  {
    const int size = L.size();

    vector< pair<int, int> > v;

    for (int bit = 1; bit < (int)(1 << size); ++bit) {
      int mn = 0;
      int mx = 0;
      for (int i = 0; i < (int)size; ++i) {
        if (bit & (1 << i)) {
          mx += U[i];
          mn += L[i];
        }
      }
      if (9001 <= mx) {
        v.push_back(make_pair(max(9001, mn), mx));
      }
    }

    sort(v.begin(), v.end());

    for (int i = 0; i + 1 < (int)v.size(); ++i) {
      if (v[i+1].first <= v[i].second) {
        v[i].second = max(v[i].second, v[i + 1].second);
        v.erase(v.begin() + i + 1);
        i = -1;
      }
    }

    int sum = 0;
    for (int i = 0; i < (int)v.size(); ++i) {
      sum += v[i].second - v[i].first + 1;
    }

    return sum;
  }