oj.uz

Submission #84415

# Submission time Handle Problem Language Result Execution time Memory
84415 2018-11-15T07:11:59 Z MrTEK Schools (IZhO13_school) C++14
30 / 100
 440 ms 18128 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 3e5 + 5;

multiset <int> l1,l2,r1,r2;
multiset <int> :: iterator it;

int n,m,s,a[N],b[N],id[N];
ll suml,sumr,ans;

void add_l(int x){
  if (l1.size() < m) {
    suml += a[x];
    l1.insert(-a[x]);
  }
  else {
    it = l1.end();
    it--;
    if (-*it < a[x]) {
      suml += a[x];
      suml -= -*it;
      l2.insert(*it);
      l1.erase(it);
      l1.insert(-a[x]);
    }
    else {
      l2.insert(-a[x]);
    }
  }
}

void add_r(int x) {
  if (r1.size() < s) {
    sumr += b[x];
    r1.insert(-b[x]);
  }
  else {
    it = r1.end();
    it--;
    if (-*it < b[x]) {
      sumr += b[x];
      sumr -= -*it;
      r2.insert(*it);
      r1.erase(it);
      r1.insert(-b[x]);
    }
    else
      r2.insert(-b[x]);
  }
}

void remove_r(int x) {
  if (r2.empty()) {
    sumr -= b[x];
    r1.erase(r1.find(-b[x]));
  }
  else {
    it = r2.find(-b[x]);
    if (it != r2.end())
      r2.erase(it);
    else {
      sumr -= b[x];
      r1.erase(r1.find(-b[x]));
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> m >> s;
  for (int i = 1 ; i <= n ; i++) {
    cin >> a[i] >> b[i];
    id[i] = i;
  }
  sort(id + 1,id + n + 1,[&](int x,int y) {
    return a[x] - a[y] > b[x] - b[y];
  });
  for (int i = 1 ; i <= m ; i++)
    add_l(id[i]);
  for (int i = m + 1 ; i <= n ; i++)
    add_r(id[i]);
  ans = suml + sumr;
  for (int i = m + 1 ; i <= n ; i++) {
    if (n - i < s)
      break;
    add_l(id[i]);
    remove_r(id[i]);
    ans = max(ans,suml + sumr);
  }
  cout << ans << "\n";
}

Compilation message

school.cpp: In function 'void add_l(int)':
school.cpp:17:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (l1.size() < m) {
       ~~~~~~~~~~^~~
school.cpp: In function 'void add_r(int)':
school.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (r1.size() < s) {
       ~~~~~~~~~~^~~

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 444 KB Output is correct
4 Incorrect 2 ms 464 KB Output isn't correct
5 Incorrect 2 ms 480 KB Output isn't correct
6 Incorrect 3 ms 608 KB Output isn't correct
7 Incorrect 6 ms 752 KB Output isn't correct
8 Correct 3 ms 812 KB Output is correct
9 Incorrect 5 ms 892 KB Output isn't correct
10 Incorrect 5 ms 892 KB Output isn't correct
11 Incorrect 5 ms 892 KB Output isn't correct
12 Incorrect 5 ms 892 KB Output isn't correct
13 Incorrect 27 ms 2652 KB Output isn't correct
14 Incorrect 119 ms 5180 KB Output isn't correct
15 Correct 326 ms 9916 KB Output is correct
16 Correct 184 ms 11220 KB Output is correct
17 Incorrect 253 ms 13384 KB Output isn't correct
18 Incorrect 333 ms 14828 KB Output isn't correct
19 Incorrect 359 ms 15960 KB Output isn't correct
20 Incorrect 440 ms 18128 KB Output isn't correct