SRM588 Div2 Medium

500

view plainprint?

1. class GUMIAndSongsDiv2 {  
2. public:  
3.   int maxSongs(vector <int> D, vector <int> ts, int T)  
4.   {  
5.     const int N = D.size();  
6.     const int BIT = 1 << N;  
7.   
8.     int ret = 0;  
9.   
10.     for (int bit = 0; bit < BIT; ++bit) {  
11.       vector<lli> v;  
12.       lli sum = 0;  
13.       for (int i = 0; i < N; ++i) {  
14.         if (bit & (1 << i)) {  
15.           sum += D[i];  
16.           v.push_back(ts[i]);  
17.         }  
18.       }  
19.       sort(v.begin(), v.end());  
20.       for (int i = 0; i + 1 < v.size(); ++i) {  
21.         sum += abs(v[i] - v[i + 1]);  
22.       }  
23.       if (sum <= T) {  
24.   
25.         ret = max(ret, __builtin_popcount(bit));  
26.       }  
27.     }  
28.     return ret;  
29.   }  

class GUMIAndSongsDiv2 {
public:
  int maxSongs(vector <int> D, vector <int> ts, int T)
  {
    const int N = D.size();
    const int BIT = 1 << N;

    int ret = 0;

    for (int bit = 0; bit < BIT; ++bit) {
      vector<lli> v;
      lli sum = 0;
      for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) {
          sum += D[i];
          v.push_back(ts[i]);
        }
      }
      sort(v.begin(), v.end());
      for (int i = 0; i + 1 < v.size(); ++i) {
        sum += abs(v[i] - v[i + 1]);
      }
      if (sum <= T) {

        ret = max(ret, __builtin_popcount(bit));
      }
    }
    return ret;
  }