oj.uz

Submission #84424

# Submission time Handle Problem Language Result Execution time Memory
84424 2018-11-15T07:30:06 Z MrTEK Schools (IZhO13_school) C++14
5 / 100
 355 ms 18172 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()) {
    if (r1.end() != r1.find(-b[x])) {
      sumr -= b[x];
      r1.erase(r1.find(-b[x]));
    }
  }
  else {
    it = r2.find(-b[x]);
    if (it != r2.end())
      r2.erase(it);
    else if (r1.end() != r1.find(-b[x])) {
        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];
  });
  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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Correct 2 ms 448 KB Output is correct
3 Incorrect 2 ms 448 KB Output isn't correct
4 Incorrect 2 ms 476 KB Output isn't correct
5 Incorrect 2 ms 552 KB Output isn't correct
6 Incorrect 2 ms 592 KB Output isn't correct
7 Incorrect 7 ms 864 KB Output isn't correct
8 Incorrect 4 ms 864 KB Output isn't correct
9 Incorrect 4 ms 864 KB Output isn't correct
10 Incorrect 4 ms 864 KB Output isn't correct
11 Incorrect 5 ms 864 KB Output isn't correct
12 Incorrect 7 ms 864 KB Output isn't correct
13 Incorrect 24 ms 2656 KB Output isn't correct
14 Incorrect 104 ms 5296 KB Output isn't correct
15 Incorrect 273 ms 9952 KB Output isn't correct
16 Incorrect 158 ms 11104 KB Output isn't correct
17 Incorrect 198 ms 13440 KB Output isn't correct
18 Incorrect 328 ms 14816 KB Output isn't correct
19 Incorrect 325 ms 15908 KB Output isn't correct
20 Incorrect 355 ms 18172 KB Output isn't correct