Submission #994411

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
994411	2024-06-07T14:48:43 Z	vjudge1	Schools (IZhO13_school)	C++17	100 / 100	161 ms	13900 KB

school

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  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> o(N);
  iota(o.begin(), o.end(), 0);
  sort(o.begin(), o.end(), [&](int x, int y) {
    return A[x] - B[x] > A[y] - B[y];
  });
  vector<ll> pf(N + 1), sf(N + 1);
  priority_queue<pair<int, int>> Q;
  ll sum_a = 0, sum_b = 0;
  for (int i = 0; i < N; i++) {
    Q.push({-A[o[i]], i});
    sum_a += A[o[i]];
    while (int(Q.size()) > M) {
      sum_a -= A[o[Q.top().second]];
      Q.pop();
    }
    pf[i + 1] = sum_a;
  }
  Q = priority_queue<pair<int, int>>();
  for (int i = N - 1; i >= 0; i--) {
    Q.push({-B[o[i]], i});
    sum_b += B[o[i]];
    while (int(Q.size()) > S) {
      sum_b -= B[o[Q.top().second]];
      Q.pop();
    }
    sf[i] = sum_b;
  }
  ll answer = numeric_limits<int>::min();
  for (int i = 0; i <= N; i++) {
    answer = max(answer, pf[i] + sf[i]);
  }
  cout << answer << "\n";
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	3 ms	520 KB	Output is correct
8	Correct	3 ms	604 KB	Output is correct
9	Correct	3 ms	604 KB	Output is correct
10	Correct	3 ms	604 KB	Output is correct
11	Correct	3 ms	604 KB	Output is correct
12	Correct	3 ms	604 KB	Output is correct
13	Correct	18 ms	2160 KB	Output is correct
14	Correct	42 ms	3820 KB	Output is correct
15	Correct	79 ms	6484 KB	Output is correct
16	Correct	95 ms	9384 KB	Output is correct
17	Correct	114 ms	10656 KB	Output is correct
18	Correct	130 ms	11244 KB	Output is correct
19	Correct	135 ms	12348 KB	Output is correct
20	Correct	161 ms	13900 KB	Output is correct