結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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))// functiontemplate <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/010000template <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_impltemplate <typename T>struct NdvectorImpl<T, 1> {using type = std::vector<T>;}; // struct ndvector_impltemplate <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_LOGGERsigned main(int argc, char* argv[]) {(void)argc;#ifdef USE_STACK_TRACE_LOGGERgoogle::InitGoogleLogging(argv[0]);google::InstallFailureSignalHandler();#else(void)argv;#endif // USE_STACK_TRACE_LOGGERint64_t N;In(N);vector<int64_t> A(N);rep(i, N) In(A[i]);#if 0set<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;}#endifset<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;}