oj.uz

Submission #84421

# Submission time Handle Problem Language Result Execution time Memory
84421 2018-11-15T07:18:35 Z MrTEK Schools (IZhO13_school) C++14
30 / 100
 447 ms 18256 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) {
    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 <= n ; i++) {
  //   cerr << id[i] << " " << a[id[i]] << " " << b[id[i]] << endl;
  // }
  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 448 KB Output is correct
4 Incorrect 2 ms 524 KB Output isn't correct
5 Incorrect 2 ms 544 KB Output isn't correct
6 Incorrect 2 ms 620 KB Output isn't correct
7 Incorrect 6 ms 876 KB Output isn't correct
8 Correct 4 ms 876 KB Output is correct
9 Incorrect 4 ms 876 KB Output isn't correct
10 Incorrect 5 ms 876 KB Output isn't correct
11 Incorrect 5 ms 876 KB Output isn't correct
12 Incorrect 5 ms 1004 KB Output isn't correct
13 Incorrect 30 ms 2684 KB Output isn't correct
14 Incorrect 123 ms 5232 KB Output isn't correct
15 Correct 354 ms 9968 KB Output is correct
16 Correct 158 ms 11260 KB Output is correct
17 Incorrect 248 ms 13564 KB Output isn't correct
18 Incorrect 342 ms 14716 KB Output isn't correct
19 Incorrect 345 ms 15888 KB Output isn't correct
20 Incorrect 447 ms 18256 KB Output isn't correct