oj.uz

Submission #873761

# Submission time Handle Problem Language Result Execution time Memory
873761 2023-11-15T16:54:12 Z MilosMilutinovic Schools (IZhO13_school) C++14
25 / 100
 194 ms 25684 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, s;
  cin >> n >> m >> s;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return a[i] > a[j] || (a[i] == a[j] && b[i] < b[j]);
  });
  vector<int> new_a(n), new_b(n);
  for (int i = 0; i < n; i++) {
    new_a[i] = a[order[i]];
    new_b[i] = b[order[i]];
  }
  a = new_a;
  b = new_b;
  order.clear();
  for (int i = m; i < n; i++) {
    order.push_back(i);
  }
  sort(order.begin(), order.end(), [&](int i, int j) {
    return b[i] > b[j];
  });
  long long ans = 0;
  for (int i = 0; i < m; i++) {
    ans += a[i];
  }
  for (int i = 0; i < s; i++) {
    ans += b[order[i]];
  }
  multiset<int> L;
  for (int i = 0; i < m; i++) {
    L.insert(-a[i] + b[i]);
  }
  multiset<pair<int, int>> R;
  multiset<int> Ra;
  multiset<pair<int, int>> Rab;
  for (int i = 0; i < s; i++) {
    R.emplace(-b[order[i]], order[i]);
    Rab.emplace(-b[order[i]] + a[order[i]], order[i]);
  }
  for (int i = s; i < (int) order.size(); i++) {
    Ra.insert(a[order[i]]);
  }
  long long res = ans;
  while (!L.empty() && !R.empty()) {
    assert(!Rab.empty());
    res += *prev(L.end());
    L.erase(prev(L.end()));
    if (Ra.empty() || prev(Rab.end())->first > prev(R.end())->first + *prev(Ra.end())) {
      auto it = prev(Rab.end());
      res += it->first;
      int i = it->second;
      R.erase(R.find({-b[i], i}));
      Rab.erase(it);
      Ra.insert(a[i]);
    } else {
      {
        auto it = prev(R.end());
        res += it->first;
        int i = it->second;
        R.erase(R.find({-b[i], i}));
        Rab.erase(Rab.find({-b[i] + a[i], i}));
      }
      {
        auto it = prev(Ra.end());
        res += *it;
        Ra.erase(it);
      }
    }
    ans = max(ans, res);
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Incorrect 2 ms 604 KB Output isn't correct
8 Incorrect 2 ms 604 KB Output isn't correct
9 Incorrect 2 ms 604 KB Output isn't correct
10 Incorrect 3 ms 604 KB Output isn't correct
11 Incorrect 2 ms 860 KB Output isn't correct
12 Incorrect 2 ms 860 KB Output isn't correct
13 Incorrect 14 ms 2800 KB Output isn't correct
14 Incorrect 40 ms 6492 KB Output isn't correct
15 Correct 87 ms 11088 KB Output is correct
16 Incorrect 178 ms 19796 KB Output isn't correct
17 Incorrect 150 ms 20036 KB Output isn't correct
18 Incorrect 153 ms 20048 KB Output isn't correct
19 Incorrect 191 ms 22356 KB Output isn't correct
20 Incorrect 194 ms 25684 KB Output isn't correct