結果

問題 No.1095 Smallest Kadomatsu Subsequence
ユーザー kyawashell
提出日時 2020-06-26 21:48:12
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 690 ms / 2,000 ms
コード長 7,239 bytes
コンパイル時間 3,865 ms
コンパイル使用メモリ 119,208 KB
最終ジャッジ日時 2025-01-11 11:13:27
ジャッジサーバーID
(参考情報)
judge5 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdint.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>
#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
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]);
#if 0
set<int64_t> left, right;
set<int64_t, greater<int64_t>> left_g, right_g;
rep(i, N) {
right.insert(A[i]);
right_g.insert(A[i]);
}
int64_t ans = numeric_limits<int64_t>::max();
rep(i, N) {
right.erase(A[i]);
right_g.erase(A[i]);
int64_t B = A[i];
{
auto it_l = left.upper_bound(A[i]);
auto it_r = right.upper_bound(A[i]);
if (it_l != left.end() && it_r != right.end()) {
cout << "a " << (*it_l) << " " << B << " " << (*it_r) << endl;
ChMin(ans, (*it_l) + (*it_r) + B);
}
}
{
auto it_l = left_g.upper_bound(A[i]);
auto it_r = right_g.upper_bound(A[i]);
if (it_l != left_g.end() && it_r != right_g.end()) {
cout << "b " << (*it_l) << " " << B << " " << (*it_r) << endl;
ChMin(ans, (*it_l) + (*it_r) + B);
}
}
left.insert(A[i]);
left_g.insert(A[i]);
}
if (ans == numeric_limits<int64_t>::max()) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
#endif
set<int64_t> left, right;
// set<int64_t, greater<int64_t>> left_g, right_g;
rep(i, N) { right.insert(A[i]); }
int64_t ans = numeric_limits<int64_t>::max();
rep(i, N) {
right.erase(A[i]);
int64_t B = A[i];
{
auto it_l = left.upper_bound(A[i]);
auto it_r = right.upper_bound(A[i]);
if (it_l != left.end() && it_r != right.end()) {
ChMin(ans, (*it_l) + (*it_r) + B);
}
}
{
auto it_l = left.begin();
auto it_r = right.begin();
if (it_l != left.end() && it_r != right.end() && (*it_l) < B &&
(*it_r) < B) {
ChMin(ans, (*it_l) + (*it_r) + B);
}
}
left.insert(A[i]);
}
if (ans == numeric_limits<int64_t>::max()) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return EXIT_SUCCESS;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0