oj.uz

Submission #676307

# Submission time Handle Problem Language Result Execution time Memory
676307 2022-12-30T08:54:45 Z vjudge1 Schools (IZhO13_school) C++17
100 / 100
 203 ms 13796 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 3e5 + 5;
 
/*
    i < j
    a[i] + b[j] > a[j] + b[i]
<=> a[i] - a[j] > b[i] - b[j]
--> just choose prefix
*/
 
int id[N];
int a[N], b[N];
int n, m, s;
int64_t pre[N], suf[N];
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
 
  cin >> n >> m >> s;
 
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
  }
 
  iota(id + 1, id + n + 1, 1);
  sort(id + 1, id + n + 1, [&](int i, int j) {
    return a[i] - a[j] > b[i] - b[j];
  });
 
  {
    multiset<int> ss;
    int64_t cur = 0;
    for (int i = 1; i <= n; i++) {
      cur += a[id[i]];
      ss.insert(a[id[i]]);
      if (ss.size() > m) {
        cur -= *ss.begin();
        ss.erase(ss.begin());
      }
      pre[i] = cur;
    }
  }
 
  {
    multiset<int> ss;
    int64_t cur = 0;
    for (int i = n; i >= 1; i--) {
      cur += b[id[i]];
      ss.insert(b[id[i]]);
      if (ss.size() > s) {
        cur -= *ss.begin();
        ss.erase(ss.begin());
      }
      suf[i] = cur;
    }
  }
 
  int64_t best = 0;
  for (int i = m; i <= n - s; i++) {
    best = max(best, pre[i] + suf[i + 1]);
  }
 
  cout << best;
 
  return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:39:21: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |       if (ss.size() > m) {
      |           ~~~~~~~~~~^~~
school.cpp:53:21: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |       if (ss.size() > s) {
      |           ~~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 3 ms 660 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 18 ms 2748 KB Output is correct
14 Correct 33 ms 3368 KB Output is correct
15 Correct 61 ms 4940 KB Output is correct
16 Correct 114 ms 12664 KB Output is correct
17 Correct 142 ms 11344 KB Output is correct
18 Correct 142 ms 11228 KB Output is correct
19 Correct 157 ms 12100 KB Output is correct
20 Correct 203 ms 13796 KB Output is correct