SRM539 Div1 Easy

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

view plainprint?

1. class Over9000Rocks {  
2. public:  
3.   int countPossibilities(vector <int> L, vector <int> U)  
4.   {  
5.     const int size = L.size();  
6.   
7.     vector< pair<int, int> > v;  
8.   
9.     for (int bit = 1; bit < (int)(1 << size); ++bit) {  
10.       int mn = 0;  
11.       int mx = 0;  
12.       for (int i = 0; i < (int)size; ++i) {  
13.         if (bit & (1 << i)) {  
14.           mx += U[i];  
15.           mn += L[i];  
16.         }  
17.       }  
18.       if (9001 <= mx) {  
19.         v.push_back(make_pair(max(9001, mn), mx));  
20.       }  
21.     }  
22.   
23.     sort(v.begin(), v.end());  
24.   
25.     for (int i = 0; i + 1 < (int)v.size(); ++i) {  
26.       if (v[i+1].first <= v[i].second) {  
27.         v[i].second = max(v[i].second, v[i + 1].second);  
28.         v.erase(v.begin() + i + 1);  
29.         i = -1;  
30.       }  
31.     }  
32.   
33.     int sum = 0;  
34.     for (int i = 0; i < (int)v.size(); ++i) {  
35.       sum += v[i].second - v[i].first + 1;  
36.     }  
37.   
38.     return sum;  
39.   }  

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;
  }