結果
問題 | No.2639 Longest Increasing Walk |
ユーザー |
|
提出日時 | 2024-02-19 21:26:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 253 ms / 2,000 ms |
コード長 | 6,635 bytes |
コンパイル時間 | 3,217 ms |
コンパイル使用メモリ | 265,772 KB |
実行使用メモリ | 34,560 KB |
最終ジャッジ日時 | 2024-09-29 01:22:44 |
合計ジャッジ時間 | 6,577 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#line 2 "/home/shogo314/cpp_include/ou-library/io.hpp"/*** @file io.hpp* @brief 空白区切り出力、iostreamのオーバーロード*/#include <array>#include <iostream>#include <utility>#include <tuple>#include <vector>namespace tuple_io {template <typename Tuple, size_t I, typename CharT, typename Traits>std::basic_istream<CharT, Traits>& read_tuple(std::basic_istream<CharT, Traits>& is, Tuple& t) {is >> std::get<I>(t);if constexpr (I + 1 < std::tuple_size_v<Tuple>) {return read_tuple<Tuple, I + 1>(is, t);}return is;}template <typename Tuple, size_t I, typename CharT, typename Traits>std::basic_ostream<CharT, Traits>& write_tuple(std::basic_ostream<CharT, Traits>& os, const Tuple& t) {os << std::get<I>(t);if constexpr (I + 1 < std::tuple_size_v<Tuple>) {os << CharT(' ');return write_tuple<Tuple, I + 1>(os, t);}return os;}};template <typename T1, typename T2, typename CharT, typename Traits>std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::pair<T1, T2>& p) {is >> p.first >> p.second;return is;}template <typename... Types, typename CharT, typename Traits>std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::tuple<Types...>& p) {return tuple_io::read_tuple<std::tuple<Types...>, 0>(is, p);}template <typename T, size_t N, typename CharT, typename Traits>std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::array<T, N>& a) {for(auto& e : a) is >> e;return is;}template <typename T, typename CharT, typename Traits>std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::vector<T>& v) {for(auto& e : v) is >> e;return is;}template <typename T1, typename T2, typename CharT, typename Traits>std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::pair<T1, T2>& p) {os << p.first << CharT(' ') << p.second;return os;}template <typename... Types, typename CharT, typename Traits>std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::tuple<Types...>& p) {return tuple_io::write_tuple<std::tuple<Types...>, 0>(os, p);}template <typename T, size_t N, typename CharT, typename Traits>std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::array<T, N>& a) {for(size_t i = 0; i < N; ++i) {if(i) os << CharT(' ');os << a[i];}return os;}template <typename T, typename CharT, typename Traits>std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::vector<T>& v) {for(size_t i = 0; i < v.size(); ++i) {if(i) os << CharT(' ');os << v[i];}return os;}/*** @brief 空行出力*/void print() { std::cout << '\n'; }/*** @brief 出力して改行** @tparam T 型* @param x 出力する値*/template <typename T>void print(const T& x) { std::cout << x << '\n'; }/*** @brief 空白区切りで出力して改行** @tparam T 1つ目の要素の型* @tparam Tail 2つ目以降の要素の型* @param x 1つ目の要素* @param tail 2つ目以降の要素*/template <typename T, typename... Tail>void print(const T& x, const Tail&... tail) {std::cout << x << ' ';print(tail...);}#line 1 "/home/shogo314/cpp_include/sh-library/base.hpp"#include <bits/stdc++.h>#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")using namespace std;using ll = long long;using ull = unsigned long long;using str = string;using pl = pair<ll, ll>;template <typename T>using ml = map<ll, T>;using mll = map<ll, ll>;using sl = set<ll>;using ld = long double;using pd = pair<ld, ld>;template <typename T>using vec = vector<T>;template <typename T>using vv = vector<vector<T>>;template <typename T>using vvv = vector<vector<vector<T>>>;template <typename T1, typename T2>using vp = vector<pair<T1, T2>>;using vl = vec<ll>;using vvl = vv<ll>;using vvvl = vvv<ll>;using vs = vec<str>;using vc = vec<char>;using vi = vec<int>;using vb = vec<bool>;using vpl = vec<pl>;using spl = set<pl>;using vd = vec<ld>;using vpd = vec<pd>;template <typename T, int N>using ary = array<T, N>;template <int N>using al = array<ll, N>;template <int N1, int N2>using aal = array<array<ll, N2>, N1>;template <int N>using val = vec<al<N>>;#define all(obj) (obj).begin(), (obj).end()#define reps(i, a, n) for (ll i = (a); i < ll(n); i++)#define rep(i, n) reps(i, 0, (n))#define rrep(i, n) reps(i, 1, (n) + 1)#define repds(i, a, n) for (ll i = ((n) - 1); i >= (a); i--)#define repd(i, n) repds(i, 0, (n))#define rrepd(i, n) repds(i, 1, (n) + 1)#define rep2(i, j, x, y) rep(i, x) rep(j, y)template <typename T1, typename T2>inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b;return true;}return false;}template <typename T1, typename T2>inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b;return true;}return false;}#define LL(x) ll x;cin >> x;#define VL(a,n) vl a(n);cin >> a;#define AL(a,k) al<k> a;cin >> a;#define VC(a,n) vc a(n);cin >> a;#define VS(a,n) vs a(n);cin >> a;#define STR(s) str s;cin >> s;#define VPL(a,n) vpl a(n);cin >> a;#define VAL(a,n,k) val<k> a(n);cin >> a;#define VVL(a,n,m) vvl a(n,vl(m));cin >> a;#define SL(a,n) sl a;{VL(b,n);a=sl(all(b));}template <typename T>using heap_max = priority_queue<T, vec<T>, less<T>>;template <typename T>using heap_min = priority_queue<T, vec<T>, greater<T>>;#line 3 "main.cpp"void solve() {LL(H);LL(W);VVL(A, H, W);ml<vpl> m;rep2(i, j, H, W) {m[A[i][j]].push_back({i, j});}vvl dp(H, vl(W));for (const auto& [_, v] : m) {for (auto [i, j] : v) {for (auto [di, dj] : vpl{{-1, 0}, {1, 0}, {0, 1}, {0, -1}}) {if (i + di < 0) continue;if (i + di >= H) continue;if (j + dj < 0) continue;if (j + dj >= W) continue;if (A[i][j] > A[i + di][j + dj]) {chmax(dp[i][j], dp[i + di][j + dj] + 1);}}}}ll ans = 0;rep2(i, j, H, W) {chmax(ans, dp[i][j]);}print(ans + 1);}int main() {cin.tie(nullptr);ios_base::sync_with_stdio(false);solve();}