結果

問題 No.972 選び方のスコア
ユーザー kyawashellkyawashell
提出日時 2020-06-27 15:53:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 125 ms / 2,000 ms
コード長 6,435 bytes
コンパイル時間 977 ms
コンパイル使用メモリ 95,624 KB
実行使用メモリ 6,484 KB
最終ジャッジ日時 2023-09-19 03:52:49
合計ジャッジ時間 7,383 ms
ジャッジサーバーID
(参考情報)
judge15 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 125 ms
6,160 KB
testcase_01 AC 125 ms
6,248 KB
testcase_02 AC 118 ms
5,896 KB
testcase_03 AC 58 ms
4,584 KB
testcase_04 AC 116 ms
6,260 KB
testcase_05 AC 117 ms
6,464 KB
testcase_06 AC 116 ms
6,220 KB
testcase_07 AC 92 ms
5,372 KB
testcase_08 AC 109 ms
6,160 KB
testcase_09 AC 106 ms
6,056 KB
testcase_10 AC 105 ms
6,208 KB
testcase_11 AC 111 ms
6,268 KB
testcase_12 AC 111 ms
6,212 KB
testcase_13 AC 110 ms
6,216 KB
testcase_14 AC 111 ms
6,212 KB
testcase_15 AC 112 ms
6,244 KB
testcase_16 AC 113 ms
6,168 KB
testcase_17 AC 113 ms
6,212 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 113 ms
6,304 KB
testcase_20 AC 111 ms
6,484 KB
testcase_21 AC 112 ms
6,264 KB
testcase_22 AC 112 ms
5,956 KB
testcase_23 AC 112 ms
6,212 KB
testcase_24 AC 112 ms
6,468 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 AC 2 ms
4,380 KB
testcase_29 AC 2 ms
4,380 KB
testcase_30 AC 2 ms
4,376 KB
testcase_31 AC 2 ms
4,376 KB
testcase_32 AC 1 ms
4,376 KB
testcase_33 AC 1 ms
4,376 KB
testcase_34 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <stdint.h>
#include <stdlib.h>

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
using default_counter_t = int64_t;

// macro
#define let auto const&
#define overload4(a, b, c, d, name, ...) name
#define rep1(n) \
  for (default_counter_t i = 0, end_i = default_counter_t(n); i < end_i; ++i)
#define rep2(i, n)                                                           \
  for (default_counter_t i = 0, end_##i = default_counter_t(n); i < end_##i; \
       ++i)
#define rep3(i, a, b)                                    \
  for (default_counter_t i       = default_counter_t(a), \
                         end_##i = default_counter_t(b); \
       i < end_##i; ++i)
#define rep4(i, a, b, c)                                 \
  for (default_counter_t i       = default_counter_t(a), \
                         end_##i = default_counter_t(b); \
       i < end_##i; i += default_counter_t(c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define rrep1(n) \
  for (default_counter_t i = default_counter_t(n) - 1; i >= 0; --i)
#define rrep2(i, n) \
  for (default_counter_t i = default_counter_t(n) - 1; i >= 0; --i)
#define rrep3(i, a, b)                                         \
  for (default_counter_t i         = default_counter_t(b) - 1, \
                         begin_##i = default_counter_t(a);     \
       i >= begin_##i; --i)
#define rrep4(i, a, b, c)                                          \
  for (default_counter_t                                           \
           i = (default_counter_t(b) - default_counter_t(a) - 1) / \
                   default_counter_t(c) * default_counter_t(c) +   \
               default_counter_t(a),                               \
           begin_##i = default_counter_t(a);                       \
       i >= begin_##i; i -= default_counter_t(c))
#define rrep(...) \
  overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)

#define ALL(f, c, ...)                                           \
  (([&](decltype((c)) cccc) {                                    \
    return (f)(std::begin(cccc), std::end(cccc), ##__VA_ARGS__); \
  })(c))

// function
template <class C>
constexpr C& Sort(C& a) {
  std::sort(std::begin(a), std::end(a));
  return a;
}
template <class C>
constexpr auto& Min(C const& a) {
  return *std::min_element(std::begin(a), std::end(a));
}
template <class C>
constexpr auto& Max(C const& a) {
  return *std::max_element(std::begin(a), std::end(a));
}
template <class C>
constexpr auto Total(C const& c) {
  return std::accumulate(std::begin(c), std::end(c), C(0));
}
template <typename T>
auto CumSum(std::vector<T> const& v) {
  std::vector<T> a(v.size() + 1, T(0));
  for (std::size_t i = 0; i < a.size() - size_t(1); ++i) a[i + 1] = a[i] + v[i];
  return a;
}
template <typename T>
constexpr bool ChMax(T& a, T const& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
constexpr bool ChMin(T& a, T const& b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}

void In(void) { return; }

template <typename First, typename... Rest>
void In(First& first, Rest&... rest) {
  cin >> first;
  In(rest...);
  return;
}

template <class T, typename I>
void VectorIn(vector<T>& v, const I n) {
  v.resize(size_t(n));
  rep(i, v.size()) cin >> v[i];
}

void Out(void) {
  cout << "\n";
  return;
}

template <typename First, typename... Rest>
void Out(First first, Rest... rest) {
  cout << first << " ";
  Out(rest...);
  return;
}

constexpr auto yes(const bool c) { return c ? "yes" : "no"; }
constexpr auto Yes(const bool c) { return c ? "Yes" : "No"; }
constexpr auto YES(const bool c) { return c ? "YES" : "NO"; }

// http://koturn.hatenablog.com/entry/2018/08/01/010000
template <typename T, typename U>
inline std::vector<U> MakeNdVector(T n, U val) noexcept {
  static_assert(std::is_integral<T>::value,
                "[MakeNdVector] The 1st argument must be an integer");
  return std::vector<U>(std::forward<T>(n), std::forward<U>(val));
}

template <typename T, typename... Args>
inline decltype(auto) MakeNdVector(T n, Args&&... args) noexcept {
  static_assert(std::is_integral<T>::value,
                "[MakeNdVector] The 1st argument must be an integer");
  return std::vector<decltype(MakeNdVector(std::forward<Args>(args)...))>(
      std::forward<T>(n), MakeNdVector(std::forward<Args>(args)...));
}

template <typename T, std::size_t N,
          typename std::enable_if<(N > 0), std::nullptr_t>::type = nullptr>
struct NdvectorImpl {
  using type = std::vector<typename NdvectorImpl<T, N - 1>::type>;
};  // struct ndvector_impl

template <typename T>
struct NdvectorImpl<T, 1> {
  using type = std::vector<T>;
};  // struct ndvector_impl

template <typename T, std::size_t N>
using NdVector = typename NdvectorImpl<T, N>::type;

#ifdef USE_STACK_TRACE_LOGGER
#ifdef __clang__
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Weverything"
#include <glog/logging.h>
#pragma clang diagnostic pop
#endif  //__clang__
#endif  // USE_STACK_TRACE_LOGGER

#include <functional>

template <typename T>
bool C(T x) {
  (void)x;
  // 上の条件を満たす関数
  return false;
}

template <typename T>
T LowerBound(T s, T t, function<bool(T)> Comp = C<T>) {
  T lb = s - 1, ub = t;

  while (ub - lb > 1) {
    T mid = (ub + lb) / 2;  // ub lb がともに大きい時オーバフローするので注意

    (Comp(mid) ? ub : lb) = mid;
  }

  return ub;  // ub = t のときはすべてfalse
}

signed main(int argc, char* argv[]) {
  (void)argc;
#ifdef USE_STACK_TRACE_LOGGER
  google::InitGoogleLogging(argv[0]);
  google::InstallFailureSignalHandler();
#else
  (void)argv;
#endif  // USE_STACK_TRACE_LOGGER
  int64_t N;
  In(N);
  vector<int64_t> a(N);
  rep(i, N) In(a[i]);

  Sort(a);

  vector<int64_t> cum(N + 1, 0);
  rep(i, N) cum[i + 1] = cum[i] + a[i];

  int64_t ans = 0;
  rep(i, N) {
    int64_t max_l                = min(i, N - i - 1);
    function<bool(int64_t)> Comp = [&](int64_t l) {
      if (i - l - 1 < 0) {
        return true;
      }
      return a[N - l - 1] + a[i - l - 1] - 2 * a[i] < 0;
    };
    int64_t l   = LowerBound<int64_t>(0, max_l + 1, Comp);
    l           = min<int64_t>(max_l, l);
    int64_t tmp = cum[i] - cum[i - l] + cum[N] - cum[N - l] - (2 * l) * a[i];
    ChMax(ans, tmp);
  }
  cout << ans << endl;

  return EXIT_SUCCESS;
}
0