oj.uz

Submission #84426

# Submission time Handle Problem Language Result Execution time Memory
84426 2018-11-15T07:33:13 Z MrTEK Schools (IZhO13_school) C++14
30 / 100
 439 ms 18084 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 if(m == 0) {
    l2.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 if (s == 0) {
    r2.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()) {
    it = r1.find(-b[x]);
    if (it != r1.end()) {
      sumr -= -*it;
      r1.erase(it);
    }
  }
  else {
    it = r2.find(-b[x]);
    if (it != r2.end()) {
      r2.erase(it);
      return;
    }
    it = r1.find(-b[x]);
    if (it != r1.end()) {
      sumr -= -*it;
      r1.erase(it);
    }
  }
}

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) {
    if (a[x] - b[x] == a[y] - b[y])
      return a[x] >= a[y];
    return a[x] - b[x] > a[y] - 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:40: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 472 KB Output is correct
4 Incorrect 2 ms 472 KB Output isn't correct
5 Incorrect 2 ms 472 KB Output isn't correct
6 Incorrect 2 ms 472 KB Output isn't correct
7 Incorrect 6 ms 808 KB Output isn't correct
8 Correct 4 ms 808 KB Output is correct
9 Incorrect 4 ms 808 KB Output isn't correct
10 Incorrect 5 ms 928 KB Output isn't correct
11 Incorrect 5 ms 928 KB Output isn't correct
12 Incorrect 5 ms 928 KB Output isn't correct
13 Incorrect 29 ms 2668 KB Output isn't correct
14 Incorrect 111 ms 5228 KB Output isn't correct
15 Correct 334 ms 9836 KB Output is correct
16 Correct 196 ms 11352 KB Output is correct
17 Incorrect 274 ms 13436 KB Output isn't correct
18 Incorrect 327 ms 14852 KB Output isn't correct
19 Incorrect 355 ms 15836 KB Output isn't correct
20 Incorrect 439 ms 18084 KB Output isn't correct