oj.uz

Submission #84410

# Submission time Handle Problem Language Result Execution time Memory
84410 2018-11-15T07:06:40 Z MrTEK Schools (IZhO13_school) C++14
20 / 100
 465 ms 18176 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],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:16: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:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (r1.size() < s) {
       ~~~~~~~~~~^~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Incorrect 2 ms 600 KB Output isn't correct
5 Incorrect 2 ms 600 KB Output isn't correct
6 Incorrect 2 ms 600 KB Output isn't correct
7 Incorrect 5 ms 788 KB Output isn't correct
8 Correct 4 ms 916 KB Output is correct
9 Incorrect 4 ms 916 KB Output isn't correct
10 Incorrect 5 ms 916 KB Output isn't correct
11 Incorrect 5 ms 916 KB Output isn't correct
12 Incorrect 5 ms 916 KB Output isn't correct
13 Incorrect 27 ms 2768 KB Output isn't correct
14 Incorrect 113 ms 5228 KB Output isn't correct
15 Incorrect 311 ms 9964 KB Output isn't correct
16 Incorrect 162 ms 11116 KB Output isn't correct
17 Incorrect 231 ms 13408 KB Output isn't correct
18 Incorrect 358 ms 14716 KB Output isn't correct
19 Incorrect 341 ms 15996 KB Output isn't correct
20 Incorrect 465 ms 18176 KB Output isn't correct