Submission #884690

#	Time	Username	Problem	Language	Result	Execution time	Memory
884690		NeroZein	Cake 3 (JOI19_cake3)	C++17	100 / 100	3410 ms	15164 KiB

cake3

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2e5 + 5;

int n, m;
int cl, cr; 
long long best, ans; 
pair<int, int> a[N]; 
multiset<int> small, big; 

void ins(int x) {
  if ((int) big.size() < m) {
    best += x;
    big.insert(x);
    return; 
  }
  int y = *big.begin();
  if (y < x) {
    small.insert(y);
    big.erase(big.find(y)); 
    best -= y; 
    big.insert(x);
    best += x;     
  } else {
    small.insert(x); 
  }
}

void erase(int x) {
  if (!small.empty() && *small.rbegin() >= x) {
    small.erase(small.find(x)); 
    return; 
  } 
  best -= x; 
  big.erase(big.find(x)); 
  if (!small.empty()) {
    int y = *small.rbegin(); 
    small.erase(small.find(y));
    big.insert(y);
    best += y; 
  }
}

void edit(int l, int r) {
  while (cl > l) ins(a[--cl].second);
  while (cr < r) ins(a[++cr].second); 
  while (cl < l) erase(a[cl++].second);; 
  while (cr > r) erase(a[cr--].second); 
}

void solve(int l, int r, int optl, int optr) {
  if (l > r) return; 
  int mid = (l + r) / 2; 
  pair<long long, int> opt = {-LLONG_MAX, optr}; 
  for (int i = max(mid, optl); i <= optr; ++i) {
    edit(mid, i); 
    long long val = best - 2 * (a[i].first - a[mid].first);
    if (i - mid + 1 >= m) {
      opt = max(opt, make_pair(val, i));       
    }
  }
  ans = max(ans, opt.first); 
  solve(l, mid - 1, optl, opt.second); 
  solve(mid + 1, r, opt.second, optr); 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i].second >> a[i].first; 
  }
  sort(a + 1, a + 1 + n); 
  cl = 1, cr = 0; 
  ans = -LLONG_MAX;
  solve(1, n, 1, n); 
  cout << ans << '\n'; 
  return 0;
}

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