SRM561 Div1 Easy

250

maxAccepted の大きさが15しかないので、2^n通り試して貪欲に割り当てていく。

int f(vector<int> ac, vector<int> b)
{
  sort(b.begin(), b.end());
  reverse(b.begin(), b.end());

  sort(ac.begin(), ac.end());
  reverse(ac.begin(), ac.end());

  int size = min(ac.size(), b.size());
  for (int i = 0; i < size; ++i) {
    int mn = min(ac[i], b[i]);
    ac[i] -= mn;
    b[i] -=mn;
  }

  int change = accumulate(b.begin(), b.end(), 0);
  int rem = accumulate(ac.begin(), ac.end(), 0);
  return (rem <= change) ? rem : inf;
}

class ICPCBalloons {
public:
  int minRepaintings(vector <int> bCount, string bSize, vector <int> ac)
  {
    vector<int> m;
    vector<int> l;
    const int size = bCount.size();

    for (int i = 0; i < size; ++i) {
      if (bSize[i] == 'L') l.push_back(bCount[i]);
      if (bSize[i] == 'M') m.push_back(bCount[i]);
    }

    int mn = inf;
    const int BIT = 1 << ac.size();
    for (int bit = 0; bit < BIT; ++bit) {
      vector<int> a, b;
      for (int i = 0; i < ac.size(); ++i) {
        if (bit & (1 << i)) a.push_back(ac[i]);
        else b.push_back(ac[i]);
      }
      int change = f(a, m) + f(b, l);
      mn = min(mn, change);
    }
    return mn == inf ? -1 : mn;
  }
};