Submission #312503

#	Time	Username	Problem	Language	Result	Execution time	Memory
312503		nathanlee726	Cake 3 (JOI19_cake3)	C++14	100 / 100	3898 ms	11256 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

const long long inf = 1ll << 60;

class solver {
 public:
  multiset<int> already, candidate;
  long long ans;
  int m;

  solver(int m): m(m) {
    ans = 0;
  }

  void insert(int x) {
    if ((int) already.size() == m) {
      if (x > *already.begin()) {
        ans += x - *already.begin();
        candidate.insert(*already.begin());
        already.erase(already.begin());
        already.insert(x);
      } else {
        candidate.insert(x);
      }
    } else {
      already.insert(x);
      ans += x;
    }
  }

  void erase(int x) {
    if (candidate.find(x) != candidate.end()) {
      candidate.erase(candidate.find(x));
    } else {
      already.erase(already.find(x));
      ans -= x;
      if (!candidate.empty()) {
        ans += *candidate.rbegin();
        already.insert(*candidate.rbegin());
        candidate.erase(--candidate.end());
      }
    }
  }

  long long query() {
    return ans;
  }
};

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i].second >> a[i].first;
  }
  sort(a.begin(), a.end());
  int l = 0, r = -1;
  long long ans = -inf;
  solver s(m);
  auto get = [&](int ll, int rr) {
    while (r < rr) {
      s.insert(a[++r].second);
    }
    while (l > ll) {
      s.insert(a[--l].second);
    }
    while (r > rr) {
      s.erase(a[r--].second);
    }
    while (l < ll) {
      s.erase(a[l++].second);
    }
    return s.query() - 2 * (a[rr].first - a[ll].first);
  };
  function<void(int, int, int, int)> solve = [&](int l, int r, int ll, int rr) {
    if (l > r) {
      return;
    }
    int mid = (l + r) >> 1;
    long long res = -inf;
    int pos = -1;
    for (int i = ll; i <= mid - m + 1 && i <= rr; ++i) {
      long long weight = get(i, mid);
      if (res < weight) {
        res = weight;
        pos = i;
      }
    }
    ans = max(ans, res);
    solve(l, mid - 1, ll, pos);
    solve(mid + 1, r, pos, rr);
  };
  solve(m - 1, n - 1, 0, n - m);
  cout << ans << "\n";
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76