oj.uz

Submission #84417

# Submission time Handle Problem Language Result Execution time Memory
84417 2018-11-15T07:15:02 Z MrTEK Schools (IZhO13_school) C++14
30 / 100
 469 ms 18268 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) {
    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]);
  if (min(m,n) == 0) {
    cerr << "Dogru iste neden gecmiyon";
    return -1;
  }
  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 448 KB Output is correct
3 Correct 2 ms 448 KB Output is 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 552 KB Output isn't correct
7 Incorrect 7 ms 936 KB Output isn't correct
8 Correct 4 ms 936 KB Output is correct
9 Incorrect 6 ms 936 KB Output isn't correct
10 Incorrect 7 ms 936 KB Output isn't correct
11 Incorrect 5 ms 936 KB Output isn't correct
12 Incorrect 5 ms 936 KB Output isn't correct
13 Incorrect 29 ms 2616 KB Output isn't correct
14 Incorrect 131 ms 5176 KB Output isn't correct
15 Correct 342 ms 9912 KB Output is correct
16 Correct 154 ms 11188 KB Output is correct
17 Incorrect 265 ms 13512 KB Output isn't correct
18 Incorrect 348 ms 14944 KB Output isn't correct
19 Incorrect 352 ms 15844 KB Output isn't correct
20 Incorrect 469 ms 18268 KB Output isn't correct