Submission #932982

# Submission time Handle Problem Language Result Execution time Memory
932982 2024-02-24T16:58:23 Z stefanneagu Schools (IZhO13_school) C++17
5 / 100
85 ms 10092 KB
#include <bits/stdc++.h>
using namespace std;

const int nmax = 1e5 + 1;

int f[nmax];

struct str {
  int a, b, i; // iarasi ichb gipsy trap idol in str
} v[nmax], init[nmax];

bool ca(str x, str y) {
  return x.a > y.a;
}

bool cb(str x, str y) {
  return x.b > y.b;
}

int main() {
  int n, ka, kb;
  cin >> n >> ka >> kb;
  multiset<pair<int, int>> ra, rb, a, b;
  for(int i = 1; i <= n; i ++) {
    cin >> v[i].a >> v[i].b;
    v[i].i = i;
    init[i] = v[i];
  }
  sort(v + 1, v + n + 1, ca);
  for(int i = 1; i <= ka; i ++) {
    a.insert({-v[i].a, v[i].i});
    f[v[i].i] ++;
  }
  for(int i = ka + 1; i <= n; i ++) {
    ra.insert({-v[i].a, v[i].i});
  }
  sort(v + 1, v + n + 1, cb);
  for(int i = 1; i <= kb; i ++) {
    b.insert({-v[i].b, v[i].i});
    f[v[i].i] ++;
  }
  for(int i = kb + 1; i <= n; i ++) {
    rb.insert({-v[i].b, v[i].i});
  }
  while(true) {
    bool ac = 0;
    auto it = a.begin();
    while(it != a.end()) {
      int i = (*it).second, x = (*it).first;
      if(b.find({-init[i].b, i}) == b.end()) {
        it ++;
        continue;
      }
      ac = 1;
      if(!rb.size()) {
        auto cp = it;
        it ++;
        a.erase(a.lower_bound(*cp));
        a.insert((*ra.begin()));
        ra.erase(ra.lower_bound(*ra.begin()));
        continue;
      }
      if(!ra.size()) {
        b.erase(b.lower_bound({-init[i].b, i}));
        b.insert((*rb.begin()));
        rb.erase(rb.lower_bound(*rb.begin()));
        it ++;
        continue;
      }
      int na = (*ra.begin()).second,  nb = (*rb.begin()).second;
      if(init[i].a + init[nb].b > init[i].b + init[na].a) {
        // eliminam b-ul, adaugam b nou
        b.erase(b.lower_bound({-init[i].b, i}));
        b.insert((*rb.begin()));
        rb.erase(rb.lower_bound((*rb.begin())));
        it ++;
      } else {
        auto cp = it;
        it ++;
        a.erase(a.lower_bound(*cp));
        a.insert((*ra.begin()));
        ra.erase(ra.lower_bound(*ra.begin()));
      }
    }
    // cout << ac << '\n';
    if(ac == 0) {
      break;
    }
  }
  // cout << "a:\n";
  long long ans = 0;
  for(auto it : a) {
    ans += it.first;
    // cout << it.first << " " << it.second << "\n";
  }
  // cout << "\nb:\n";
  for(auto it : b) {
    ans += it.first;
    // cout << it.first << " " << it.second << '\n';
  }
  cout << -ans;
  return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:49:29: warning: unused variable 'x' [-Wunused-variable]
   49 |       int i = (*it).second, x = (*it).first;
      |                             ^
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 0 ms 2396 KB Output isn't correct
4 Incorrect 0 ms 2396 KB Output isn't correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Incorrect 3 ms 2908 KB Output isn't correct
8 Incorrect 45 ms 2908 KB Output isn't correct
9 Incorrect 10 ms 2908 KB Output isn't correct
10 Incorrect 6 ms 3000 KB Output isn't correct
11 Incorrect 4 ms 3060 KB Output isn't correct
12 Incorrect 5 ms 2804 KB Output isn't correct
13 Incorrect 85 ms 6152 KB Output isn't correct
14 Incorrect 67 ms 10092 KB Output isn't correct
15 Runtime error 57 ms 5968 KB Execution killed with signal 11
16 Runtime error 76 ms 5984 KB Execution killed with signal 11
17 Runtime error 55 ms 5964 KB Execution killed with signal 11
18 Runtime error 54 ms 5972 KB Execution killed with signal 11
19 Runtime error 60 ms 5968 KB Execution killed with signal 11
20 Runtime error 54 ms 5968 KB Execution killed with signal 11