Submission #932966

# Submission time Handle Problem Language Result Execution time Memory
932966 2024-02-24T16:24:11 Z stefanneagu Schools (IZhO13_school) C++17
5 / 100
77 ms 11092 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;
  set<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(*cp);
        a.insert((*ra.begin()));
        ra.erase((*ra.begin()));
        continue;
      }
      if(!ra.size()) {
        b.erase({-init[i].b, i});
        b.insert((*rb.begin()));
        rb.erase((*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({-init[i].b, i});
        b.insert((*rb.begin()));
        rb.erase((*rb.begin()));
        it ++;
      } else {
        auto cp = it;
        it ++;
        a.erase(*cp);
        a.insert((*ra.begin()));
        ra.erase((*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 1 ms 2396 KB Output is correct
3 Incorrect 0 ms 2396 KB Output isn't correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Incorrect 1 ms 2392 KB Output isn't correct
7 Incorrect 4 ms 2908 KB Output isn't correct
8 Incorrect 39 ms 2908 KB Output isn't correct
9 Incorrect 10 ms 2908 KB Output isn't correct
10 Incorrect 5 ms 2904 KB Output isn't correct
11 Incorrect 4 ms 2908 KB Output isn't correct
12 Incorrect 4 ms 2908 KB Output isn't correct
13 Incorrect 77 ms 6544 KB Output isn't correct
14 Incorrect 62 ms 11092 KB Output isn't correct
15 Runtime error 62 ms 7500 KB Execution killed with signal 11
16 Runtime error 52 ms 7496 KB Execution killed with signal 11
17 Runtime error 54 ms 7620 KB Execution killed with signal 11
18 Runtime error 64 ms 7768 KB Execution killed with signal 11
19 Runtime error 56 ms 7684 KB Execution killed with signal 11
20 Runtime error 55 ms 7612 KB Execution killed with signal 11