제출 #1117371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117371		stefanneagu	학교 설립 (IZhO13_school)	C++17	20 / 100	583 ms	46512 KiB

school

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int nmax = 3e5 + 1;

struct str {
  int a, b;
} v[nmax];

bool fa[nmax], fb[nmax];

int32_t main() {
  int n, a, b;
  cin >> n >> a >> b;
  set<pair<int, int>> ra, rb;
  for(int i = 1; i <= n; i++) {
    cin >> v[i].a >> v[i].b;
    v[i].a = -v[i].a, v[i].b = -v[i].b;
    ra.insert({v[i].a, i});
    rb.insert({v[i].b, i});
  }
  for(int i = 1; i <= a; i++) {
    auto [val, poz] = *ra.begin();
    fa[poz] = 1;
    ra.erase({val, poz});
  }
  for(int i = 1; i <= b; i++) {
    auto [val, poz] = *rb.begin();
    fb[poz] = 1;
    rb.erase({val, poz});
  }
  for(int i = 1; i <= n; i++) {
    if(fa[i] || fb[i]) {
      // mereu o sa fie marcat?
      ra.erase({v[i].a, i});
      rb.erase({v[i].b, i});
    }
  }
  for(int i = 1; i <= n; i++) {
    if(fa[i] == 1 && fb[i] == 1) {
      int difa = v[i].a - (*ra.begin()).first;
      int difb = v[i].b - (*rb.begin()).first;
      // cout << "! " << difa << " " << difb << '\n';
      if(difa > difb) {
        fa[i] = 0;
        auto [val, poz] = *ra.begin();
        fa[poz] = 1;
        ra.erase({val, poz});
        rb.erase({v[poz].b, poz});
      } else if(difa < difb) {
        fb[i] = 0;
        auto [val, poz] = *rb.begin();
        fb[poz] = 1;
        rb.erase({val, poz});
        ra.erase({v[poz].a, poz});
      } else if(v[i].a < v[i].b) {
        fa[i] = 0;
        auto [val, poz] = *ra.begin();
        fa[poz] = 1;
        ra.erase({val, poz});
        rb.erase({v[poz].b, poz});
      } else {
        fa[i] = 0;
        auto [val, poz] = *ra.begin();
        fa[poz] = 1;
        ra.erase({val, poz});
        rb.erase({v[poz].b, poz});
      }
    }
  }
  long long ans = 0;
  for(int i = 1; i <= n; i++) {
    // cout << fa[i] << " " << fb[i] << '\n';
    ans += fa[i] * v[i].a + fb[i] * v[i].b;
  }
  cout << -ans;
	return 0;
}

• Subtask 1: 20 / 100