oj.uz

Submission #1117400

# Submission time Handle Problem Language Result Execution time Memory
1117400 2024-11-23T13:53:33 Z stefanneagu Schools (IZhO13_school) C++17
100 / 100
 264 ms 17324 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 3e5 + 1;

struct str {
  int dif, a, b;
} v[nmax];

bool cmp(str x, str y) {
  return x.dif > y.dif;
}

int dp1[nmax], dp2[nmax];

int32_t main() {
  int n, m, s;
  cin >> n >> m >> s;
  for(int i = 1; i <= n; i++) {
    cin >> v[i].a >> v[i].b;
    v[i].dif = v[i].a - v[i].b;
  }
  sort(v + 1, v + n + 1, cmp);
  multiset<int> ms;
  int sum = 0;
  for(int i = 1; i <= n; i++) {
    ms.insert(v[i].a);
    sum += v[i].a;
    if(ms.size() > m) {
      sum -= *ms.begin();
      ms.erase(ms.lower_bound(*ms.begin()));
    }
    dp1[i] = sum;
    // cout << i <<  ": " << dp1[i] << '\n';
  }
  // cout << '\n';
  ms.clear();
  sum = 0;
  for(int i = n; i >= 1; i--) {
    ms.insert(v[i].b);
    sum += v[i].b;
    if(ms.size() > s) {
      sum -= *ms.begin();
      ms.erase(ms.lower_bound(*ms.begin()));
    }
    dp2[i] = sum;
    // cout << i << ": " << dp2[i] << '\n';
  }
  int ans = 0;
  for(int i = m; i <= n - s; i++) {
    ans = max(ans, dp1[i] + dp2[i + 1]);
  }
  cout << ans;
	return 0;
}

Compilation message

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 4 ms 960 KB Output is correct
9 Correct 4 ms 592 KB Output is correct
10 Correct 4 ms 592 KB Output is correct
11 Correct 5 ms 592 KB Output is correct
12 Correct 4 ms 688 KB Output is correct
13 Correct 26 ms 3244 KB Output is correct
14 Correct 49 ms 4304 KB Output is correct
15 Correct 86 ms 6728 KB Output is correct
16 Correct 161 ms 14816 KB Output is correct
17 Correct 183 ms 13740 KB Output is correct
18 Correct 195 ms 14088 KB Output is correct
19 Correct 208 ms 15176 KB Output is correct
20 Correct 264 ms 17324 KB Output is correct