oj.uz

Submission #84432

# Submission time Handle Problem Language Result Execution time Memory
84432 2018-11-15T07:40:19 Z MrTEK Schools (IZhO13_school) C++14
100 / 100
 450 ms 18284 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,it2;

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);
      if (r2.empty() == false) {
        it2 = r2.begin();
        sumr += -*it2;
        r1.insert(*it2);
        r2.erase(it2);
      }
    }
  }
}

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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 564 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 9 ms 800 KB Output is correct
8 Correct 4 ms 820 KB Output is correct
9 Correct 5 ms 820 KB Output is correct
10 Correct 5 ms 820 KB Output is correct
11 Correct 5 ms 964 KB Output is correct
12 Correct 7 ms 964 KB Output is correct
13 Correct 30 ms 2644 KB Output is correct
14 Correct 112 ms 5220 KB Output is correct
15 Correct 340 ms 9964 KB Output is correct
16 Correct 167 ms 11148 KB Output is correct
17 Correct 244 ms 13420 KB Output is correct
18 Correct 344 ms 14724 KB Output is correct
19 Correct 343 ms 15852 KB Output is correct
20 Correct 450 ms 18284 KB Output is correct