oj.uz

Submission #84407

# Submission time Handle Problem Language Result Execution time Memory
84407 2018-11-15T07:05:20 Z MrTEK Schools (IZhO13_school) C++14
20 / 100
 375 ms 36472 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],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]);
  ans = suml + sumr;
  for (int i = m + 1 ; i <= n ; i++) {
    if (n - i < s)
      break;
    add_l(i);
    remove_r(i);
    ans = max(ans,suml + sumr);
  }
  cout << ans << "\n";
}

Compilation message

school.cpp: In function 'void add_l(int)':
school.cpp:16: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:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (r1.size() < s) {
       ~~~~~~~~~~^~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Runtime error 5 ms 860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 6 ms 936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 5 ms 1032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 8 ms 1508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 6 ms 1640 KB Output is correct
9 Runtime error 8 ms 1740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 7 ms 1740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 8 ms 1740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 8 ms 1740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 30 ms 5276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 77 ms 10268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 203 ms 19820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Incorrect 165 ms 20832 KB Output isn't correct
17 Runtime error 227 ms 26908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 324 ms 29516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 325 ms 31756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 375 ms 36472 KB Execution killed with signal 11 (could be triggered by violating memory limits)