Submission #676449

#	Time	Username	Problem	Language	Result	Execution time	Memory
676449		vjudge1	Schools (IZhO13_school)	C++17	100 / 100	76 ms	7788 KiB

school

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

template <typename T> inline void read(T &n) {
  char c;

  do {
    c = getchar();
  }
  while (isdigit(c) == false && c != '-');

  bool negative = (c == '-');

  if (c == '-') {
    c = getchar();
  }

  n = 0;

  do {
    n = n * 10 + c - '0';
    c = getchar();
  }
  while (isdigit(c));

  if (negative) {
    n = -n;
  }
}

const int MAX_N = 300000;

pair <int, int> v[MAX_N + 1];

int64_t prefix[MAX_N + 1],
        suffix[MAX_N + 2];

int main() {
  int n, m, s;
  read(n); read(m); read(s);

  for (int i = 1; i <= n; i++) {
    auto &[a, b] = v[i];
    read(a); read(b);
  }

  sort(v + 1, v + n + 1, [] (auto p1, auto p2) {
    auto [a1, b1] = p1;
    auto [a2, b2] = p2;
    return (a1 - b1 > a2 - b2);
  });

  priority_queue <int, vector <int>, greater <int>> q;

  prefix[0] = 0;

  for (int i = 1; i <= n; i++) {
    auto [a, b] = v[i];

    int64_t &res = prefix[i];

    res = prefix[i - 1] + a;
    q.push(a);

    if (q.size() > m) {
      res -= q.top();
      q.pop();
    }
  }

  while (q.empty() == false) {
    q.pop();
  }

  suffix[n + 1] = 0;

  for (int i = n; i >= 1; i--) {
    auto [a, b] = v[i];

    int64_t &res = suffix[i];

    res = suffix[i + 1] + b;
    q.push(b);

    if (q.size() > s) {
      res -= q.top();
      q.pop();
    }
  }

  int64_t res = 0;

  for (int i = m; i <= n - s; i++) {
    res = max(res, prefix[i] + suffix[i + 1]);
  }

  cout << res;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:65:18: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |     if (q.size() > m) {
      |         ~~~~~~~~~^~~
school.cpp:85:18: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |     if (q.size() > s) {
      |         ~~~~~~~~~^~~

• Subtask 1: 100 / 100