#953643 (C++23) No.2639 Longest Increasing Walk

提出ソース

結果

問題	No.2639 Longest Increasing Walk
ユーザー	Re0denX
提出日時	2024-02-22 23:23:19
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	40 ms / 2,000 ms
コード長	6,528 bytes
コンパイル時間	3,333 ms
コンパイル使用メモリ	260,408 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-09-29 04:29:58
合計ジャッジ時間	4,760 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	39 ms 6,820 KB
testcase_05	AC	38 ms 6,820 KB
testcase_06	AC	37 ms 6,816 KB
testcase_07	AC	40 ms 6,816 KB
testcase_08	AC	37 ms 6,820 KB
testcase_09	AC	40 ms 6,820 KB
testcase_10	AC	25 ms 6,820 KB
testcase_11	AC	23 ms 6,816 KB
testcase_12	AC	5 ms 6,816 KB
testcase_13	AC	26 ms 6,820 KB
testcase_14	AC	16 ms 6,816 KB
testcase_15	AC	2 ms 6,816 KB
testcase_16	AC	2 ms 6,820 KB
testcase_17	AC	15 ms 6,820 KB
testcase_18	AC	19 ms 6,816 KB
testcase_19	AC	7 ms 6,816 KB
testcase_20	AC	13 ms 6,820 KB
testcase_21	AC	23 ms 6,816 KB
testcase_22	AC	9 ms 6,820 KB
testcase_23	AC	2 ms 6,816 KB
testcase_24	AC	2 ms 6,820 KB
testcase_25	AC	2 ms 6,816 KB
testcase_26	AC	2 ms 6,816 KB
testcase_27	AC	2 ms 6,820 KB
testcase_28	AC	2 ms 6,820 KB
testcase_29	AC	2 ms 6,820 KB
testcase_30	AC	2 ms 6,816 KB
testcase_31	AC	2 ms 6,820 KB
testcase_32	AC	2 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

using namespace std;
inline namespace IO {
#define SFINAE(x, ...)                                                         \
  template <class, class = void> struct x : std::false_type {};                \
  template <class T> struct x<T, std::void_t<__VA_ARGS__>> : std::true_type {}

SFINAE(DefaultI, decltype(std::cin >> std::declval<T &>()));
SFINAE(DefaultO, decltype(std::cout << std::declval<T &>()));
SFINAE(IsTuple, typename std::tuple_size<T>::type);
SFINAE(Iterable, decltype(std::begin(std::declval<T>())));

template <auto &is> struct Reader {
  template <class T> void Impl(T &t) {
    if constexpr (DefaultI<T>::value)
      is >> t;
    else if constexpr (Iterable<T>::value) {
      for (auto &x : t) Impl(x);
    } else if constexpr (IsTuple<T>::value) {
      std::apply([this](auto &...args) { (Impl(args), ...); }, t);
    } else
      static_assert(IsTuple<T>::value, "No matching type for read");
  }
  template <class... Ts> void read(Ts &...ts) { ((Impl(ts)), ...); }
};

template <class... Ts> void re(Ts &...ts) { Reader<cin>{}.read(ts...); }
#define def(t, args...)                                                        \
  t args;                                                                      \
  re(args);

template <auto &os, bool debug, bool print_nd> struct Writer {
  string comma() const { return debug ? "," : ""; }
  template <class T> constexpr char Space(const T &) const {
    return print_nd && (Iterable<T>::value or IsTuple<T>::value) ? '\n' : ' ';
  }
  template <class T> void Impl(T const &t) const {
    if constexpr (DefaultO<T>::value)
      os << t;
    else if constexpr (Iterable<T>::value) {
      if (debug) os << '{';
      int i = 0;
      for (auto &&x : t)
        ((i++) ? (os << comma() << Space(x), Impl(x)) : Impl(x));
      if (debug) os << '}';
    } else if constexpr (IsTuple<T>::value) {
      if (debug) os << '(';
      std::apply(
          [this](auto const &...args) {
            int i = 0;
            (((i++) ? (os << comma() << " ", Impl(args)) : Impl(args)), ...);
          },
          t);
      if (debug) os << ')';
    } else
      static_assert(IsTuple<T>::value, "No matching type for print");
  }
  template <class T> void ImplWrapper(T const &t) const {
    if (debug) os << "\033[0;31m";
    Impl(t);
    if (debug) os << "\033[0m";
  }
  template <class... Ts> void print(Ts const &...ts) const {
    ((Impl(ts)), ...);
  }
  template <class F, class... Ts>
  void print_with_sep(const std::string &sep, F const &f,
                      Ts const &...ts) const {
    ImplWrapper(f), ((os << sep, ImplWrapper(ts)), ...), os << '\n';
  }
  void print_with_sep(const std::string &) const { os << '\n'; }
};

template <class... Ts> void pr(Ts const &...ts) {
  Writer<cout, false, true>{}.print(ts...);
}
template <class... Ts> void ps(Ts const &...ts) {
  Writer<cout, false, true>{}.print_with_sep(" ", ts...);
}
} // namespace IO

inline namespace Debug {
template <typename... Args> void err(Args... args) {
  Writer<cerr, true, false>{}.print_with_sep(" | ", args...);
}
template <typename... Args> void errn(Args... args) {
  Writer<cerr, true, true>{}.print_with_sep(" | ", args...);
}

void err_prefix(string func, int line, string args) {
  cerr << "\033[0;31m\u001b[1mDEBUG\033[0m"
       << " | "
       << "\u001b[34m" << func << "\033[0m"
       << ":"
       << "\u001b[34m" << line << "\033[0m"
       << " - "
       << "[" << args << "] = ";
}

#ifdef LOCAL
#define dbg(args...) err_prefix(__FUNCTION__, __LINE__, #args), err(args)
#define dbgn(args...) err_prefix(__FUNCTION__, __LINE__, #args), errn(args)
#else
#define dbg(...)
#define dbgn(args...)
#endif

const auto beg_time = std::chrono::high_resolution_clock::now();
// https://stackoverflow.com/questions/47980498/accurate-c-c-clock-on-a-multi-core-processor-with-auto-overclock?noredirect=1&lq=1
double time_elapsed() {
  return chrono::duration<double>(std::chrono::high_resolution_clock::now() -
                                  beg_time)
      .count();
}
} // namespace Debug

inline namespace FileIO {
void setIn(string s) { freopen(s.c_str(), "r", stdin); }
void setOut(string s) { freopen(s.c_str(), "w", stdout); }
void setIO(string s = "") {
  cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams
  cout << fixed << setprecision(12);
  // cin.exceptions(cin.failbit);
  // throws exception when do smth illegal
  // ex. try to read letter into int
  if ((int)(s.size())) setIn(s + ".in"), setOut(s + ".out"); // for old USACO
}
} // namespace FileIO

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 42
#endif // LOCAL

struct ChronoTimer {
  std::chrono::high_resolution_clock::time_point st;

  ChronoTimer() { reset(); }

  void reset() { st = std::chrono::high_resolution_clock::now(); }

  std::chrono::milliseconds::rep elapsed() {
    auto ed = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(ed - st)
        .count();
  }
};

constexpr bool TEST = false;

namespace std {

template <class Fun> class y_combinator_result {
  Fun fun_;

public:
  template <class T>
  explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

  template <class... Args> decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template <class Fun> decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

void run_case(int tc) {
  using ll = int64_t;
  def(int, N, M);
  vector A(N, vector<int>(M));
  re(A);

  vector dp(N, vector<ll>(M, -1));
  constexpr int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

  ll ret = 0;
  for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {
    dp[i][j] = y_combinator([&](auto self, int u, int v) -> ll {
      if (~dp[u][v]) {
        return dp[u][v];
      }

      ll ans = 0;
      for (int k = 0; k < 4; k++) {
        int ii = u + dir[k][0], jj = v + dir[k][1];
        if (ii < 0 || jj < 0 || ii >= N || jj >= M) continue;
        if (A[ii][jj] < A[u][v]) ans = max(ans, self(ii, jj));
      }

      return dp[u][v] = ans + 1;
    })(i, j);
    ret = max(ret, dp[i][j]);
  }

  ps(ret);
}

int main(int, char **) {
#ifdef LOCAL
  ChronoTimer chrono;
  setIO("../src/prob");
#else
  setIO();
#endif
  int T = 1;
  if constexpr (TEST) re(T);

  for (int tc = 1; tc <= T; tc++) run_case(tc);

#ifdef LOCAL
  ps("\nRunning Time:", chrono.elapsed(), "ms");
#endif
}

yukicoder

結果

テストケース

ソースコード