提出 #25249682

---

ソースコード 拡げる

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <vector>

#include <atcoder/segtree>

using usize = size_t;

namespace RangeMaxQuery {
int64_t op(int64_t a, int64_t b) { return std::max(a, b); }
int64_t e() { return 0; }
using segtree = atcoder::segtree<int64_t, op, e>;
} // namespace RangeMaxQuery

namespace RangeMinQuery {
int64_t op(int64_t a, int64_t b) { return std::min(a, b); }
int64_t e() { return 1ll << 62; }
using segtree = atcoder::segtree<int64_t, op, e>;
} // namespace RangeMinQuery

int main(void) {
  // input
  usize N, X, Y;
  std::cin >> N >> X >> Y;
  int64_t B, C;
  std::cin >> B >> C;
  if (B < C) {
    std::swap(X, Y);
    std::swap(B, C);
  }
  std::vector<int64_t> A(N);
  for (auto &a : A)
    std::cin >> a;

  // solve
  std::sort(A.begin(), A.end());
  RangeMaxQuery::segtree seg_max(A);
  RangeMinQuery::segtree seg_min(A);
  const auto kmin = (X + Y < N ? 0 : X + Y - N);
  const auto kmax = std::min(X, Y);

  int64_t ans = 1ll << 62;
  for (usize k = kmin; k <= kmax; ++k) {
    int64_t ma = RangeMaxQuery::e(), mi = RangeMinQuery::e();

    if (k - 0 > 0)
      ma = std::max(ma, seg_max.prod(0, k) + B + C);
    if (X - k > 0)
      ma = std::max(ma, seg_max.prod(k, X) + B);
    if ((X + Y - k) - X > 0)
      ma = std::max(ma, seg_max.prod(X, X + Y - k) + C);
    if (N - (X + Y - k) > 0)
      ma = std::max(ma, seg_max.prod(X + Y - k, N));

    if (k - 0 > 0)
      mi = std::min(mi, seg_min.prod(0, k) + B + C);
    if (X - k > 0)
      mi = std::min(mi, seg_min.prod(k, X) + B);
    if ((X + Y - k) - X > 0)
      mi = std::min(mi, seg_min.prod(X, X + Y - k) + C);
    if (N - (X + Y - k) > 0)
      mi = std::min(mi, seg_min.prod(X + Y - k, N));

    ans = std::min(ans, ma - mi);
  }

  // output
  std::cout << ans << std::endl;
}

提出情報

ジャッジ結果