Submission #932996

#	Time	Username	Problem	Language	Result	Execution time	Memory
932996		stefanneagu	Schools (IZhO13_school)	C++17	5 / 100	73 ms	10064 KiB

school

#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 if(init[i].a + init[nb].b < init[i].b + init[na].a){
        auto cp = it;
        it ++;
        a.erase(a.lower_bound(*cp));
        a.insert((*ra.begin()));
        ra.erase(ra.lower_bound(*ra.begin()));
      } else {
        if(a.find({-init[nb].a, nb}) == a.end()) {
            b.erase(b.lower_bound({-init[i].b, i}));
            b.insert((*rb.begin()));
            rb.erase(rb.lower_bound((*rb.begin())));
            it ++;
        } else if(b.find({-init[na].b, na}) == b.end()) {
             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 (stderr)

school.cpp: In function 'int main()':
school.cpp:49:29: warning: unused variable 'x' [-Wunused-variable]
   49 |       int i = (*it).second, x = (*it).first;
      |                             ^

• Subtask 1: 5 / 100