Submission #1160431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160431		fryingduc	Cake 3 (JOI19_cake3)	C++20	0 / 100	0 ms	328 KiB

cake3

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, m, v[maxn], c[maxn];
int ord[maxn];

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> v[i] >> c[i];
    ord[i] = i;
  }
  sort(ord + 1, ord + n + 1, [](const int &x, const int &y) -> bool {
    return c[x] < c[y];
  });
  set<pair<long long, int>> s;
  long long sum = 0;
  int cur_mn = 1;
  set<int> cand;
  for (int i = 1; i < m; ++i) {
    if (i == 1) {
      s.insert(make_pair(1ll * v[ord[i]] + 2 * c[ord[i]], i));
    } else {
      s.insert(make_pair(v[ord[i]], i));
    }
    cand.insert(i);
  }
  for (auto i:s) {
    sum += i.first;
  }
  long long res = -1e18;
  for (int i = m; i <= n; ++i) {
    res = max(res, sum + v[ord[i]] - 2 * c[ord[i]]);
    if (v[ord[i]] >= s.begin()->first) {
      auto t = *s.begin();
      s.erase(t);
      cand.erase(t.second);
      sum -= t.first;
      sum += v[ord[i]];
      s.insert(make_pair(v[ord[i]], i));
      cand.insert(i);
      if (t.second == cur_mn) {
        cur_mn = *cand.begin();
        s.erase(s.find(make_pair(v[ord[cur_mn]], cur_mn)));
        s.insert(make_pair(1ll * v[ord[cur_mn]] + 2ll * c[ord[cur_mn]], cur_mn));
        sum += 2ll * c[ord[cur_mn]];
      }
    }
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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