oj.uz

Submission #84418

# Submission time Handle Problem Language Result Execution time Memory
84418 2018-11-15T07:15:43 Z MrTEK Schools (IZhO13_school) C++14
25 / 100
 454 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;

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,s) == 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
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 2 ms 448 KB Execution failed because the return code was nonzero
3 Correct 2 ms 448 KB Output is correct
4 Incorrect 2 ms 448 KB Output isn't correct
5 Incorrect 2 ms 456 KB Output isn't correct
6 Incorrect 2 ms 504 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 5 ms 820 KB Output isn't correct
10 Incorrect 5 ms 820 KB Output isn't correct
11 Incorrect 5 ms 820 KB Output isn't correct
12 Incorrect 5 ms 824 KB Output isn't correct
13 Incorrect 26 ms 2628 KB Output isn't correct
14 Incorrect 111 ms 5060 KB Output isn't correct
15 Correct 315 ms 9900 KB Output is correct
16 Correct 164 ms 11088 KB Output is correct
17 Incorrect 235 ms 13540 KB Output isn't correct
18 Incorrect 341 ms 14780 KB Output isn't correct
19 Incorrect 364 ms 15852 KB Output isn't correct
20 Incorrect 454 ms 18284 KB Output isn't correct