Submission #1117399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117399		stefanneagu	Schools (IZhO13_school)	C++17	75 / 100	225 ms	15176 KiB

school

#include <bits/stdc++.h>

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 (stderr)

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

• Subtask 1: 75 / 100