제출 #1316966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316966		LIA	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	9 / 100	5095 ms	18620 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (int i = s; i < e; ++i)
int n;
v<ll> a, b, c;
bool can_match(v<ll> &plants, v<ll> &pots, ll x) {
  lp(i, 0, n) {
    if (abs(plants[i] - pots[i]) > x)
      return false;
  }
  return true;
}

bool check(ll x) {
  lp(l, 0, n + 1) {
    v<ll> window_plants;
    v<ll> outside_plants;
    lp(i, 0, 2 * n) {
      if (i >= l && i < l + n) {
        window_plants.push_back(a[i]);
      } else {
        outside_plants.push_back(a[i]);
      }
    }
    sort(window_plants.begin(), window_plants.end());
    sort(outside_plants.begin(), outside_plants.end());
    if (can_match(window_plants, b, x) && can_match(outside_plants, c, x))
      return true;
    if (can_match(window_plants, c, x) && can_match(outside_plants, b, x))
      return true;
  }

  return false;
}

int main() {
  cin >> n;
  a.resize(2 * n);
  lp(i, 0, 2 * n) cin >> a[i];
  b.resize(n);
  lp(i, 0, n) cin >> b[i];
  c.resize(n);
  lp(i, 0, n) cin >> c[i];
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());
  ll lo = 0, hi = 2e9, ans = 2e9;
  while (lo <= hi) {
    ll mid = lo + (hi - lo) / 2;
    if (check(mid)) {
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  cout << ans << endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 37
• Subtask 5: 0 / 33