SRM582 Div1 Easy

250

ソートして二分探索。

class SpaceWarDiv1 {
public:
  long long minimalFatigue(vector <int> m, vector <int> es, vector<long long> ec)
  {
    sort(m.begin(), m.end());
    vector< pair<lli, lli> > v;
    for (int i = 0; i < es.size(); ++i) {
      v.push_back(make_pair(es[i], ec[i]));
    }
    sort(v.begin(), v.end());

    const lli L = 100000000000000LL * 50LL * 2LL;
    lli small = 0, large = L;

    const vector< pair<lli, lli> > tmp_v = v;
    const vector<int> tmp_m = m;

    while (small + 1 < large) {
      lli mid = (small + large) / 2;
      for (int i = 0; i < m.size(); ++i) {
        lli sum = 0;
        for (int j = 0; j < v.size(); ++j) {
          if (v[j].first <= m[i]) {
            lli a = mid - sum;
            lli b = v[j].second;
            lli c = min(a, b);
            sum += c;
            v[j].second -= c;
          }
        }
      }
      bool succ = true;
      for (int i = 0; i < v.size(); ++i) {
        succ = succ && (v[i].second == 0LL);
      }
      if (succ) large = mid;
      else small = mid;

      m = tmp_m;
      v = tmp_v;
    }

    return large == L ? -1 : large;
  }