oj.uz

Submission #84406

# Submission time Handle Problem Language Result Execution time Memory
84406 2018-11-15T07:05:04 Z MrTEK Schools (IZhO13_school) C++14
20 / 100
 524 ms 36924 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);
    cerr << ans << endl;
  }
  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 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Runtime error 5 ms 676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 5 ms 824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 5 ms 984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 8 ms 1532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 4 ms 1664 KB Output is correct
9 Runtime error 8 ms 1668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 10 ms 1832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 8 ms 1864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 9 ms 1900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 29 ms 5484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 69 ms 10476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 328 ms 20404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Incorrect 154 ms 21012 KB Output isn't correct
17 Runtime error 276 ms 27196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 350 ms 29852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 432 ms 32292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 524 ms 36924 KB Execution killed with signal 11 (could be triggered by violating memory limits)