Submission #1092101

#TimeUsernameProblemLanguageResultExecution timeMemory
1092101juicySchools (IZhO13_school)C++17
20 / 100
81 ms8788 KiB
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n, m, s; cin >> n >> m >> s;
  vector<array<int, 2>> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i][0] >> a[i][1];
  }  
  sort(a.rbegin(), a.rend());
  int p = m;
  priority_queue<int> x;
  priority_queue<array<int, 2>> y;
  long long res = 0;
  for (int i = 0; i < n; ++i) {
    if (i < m) {
      x.push(a[i][1] - a[i][0]);
      res += a[i][0];
    } else {
      y.push({a[i][1], i});
    }
  }
  vector<bool> used(n);
  while (s--) {
    if (!x.size()) {
      res += y.top()[0];
      y.pop();
    } else {
      while (y.size() && used[y.top()[1]]) {
        y.pop();
      }
      if (x.top() + a[p][0] > y.top()[0]) {
        res += x.top() + a[p][0];
        used[p++] = 1;
        x.pop();
      } else {
        auto [v, id] = y.top(); y.pop();
        res += v;
        used[id] = 1;
      }
    }
  }
  cout << res;
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...