SRM588 Div2 Medium

500

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