結果
問題 | No.2639 Longest Increasing Walk |
ユーザー |
![]() |
提出日時 | 2024-02-19 21:43:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 1,931 bytes |
コンパイル時間 | 1,878 ms |
コンパイル使用メモリ | 199,076 KB |
最終ジャッジ日時 | 2025-02-19 16:47:45 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>namespace zawa {using i16 = std::int16_t;using i32 = std::int32_t;using i64 = std::int64_t;using i128 = __int128_t;using u8 = std::uint8_t;using u16 = std::uint16_t;using u32 = std::uint32_t;using u64 = std::uint64_t;using usize = std::size_t;} // namespace zawanamespace zawa {void SetFastIO() {std::cin.tie(nullptr)->sync_with_stdio(false);}void SetPrecision(u32 dig) {std::cout << std::fixed << std::setprecision(dig);}} // namespace zawausing namespace zawa;int dx[4]{ 0, 1, 0, -1 };int dy[4]{ 1, 0, -1, 0 };int main() {SetFastIO();int h, w; std::cin >> h >> w;std::vector a(h, std::vector<int>(w));for (int i{} ; i < h ; i++) for (int j{} ; j < w ; j++) std::cin >> a[i][j];int n{h * w};auto f{[&](int x, int y) -> int {return x * w + y;}};auto in{[&](int x, int y) -> bool {return 0 <= x and x < h and 0 <= y and y < w;}};std::vector g(n, std::vector<int>{});std::vector<int> deg(n);for (int x{} ; x < h ; x++) {for (int y{} ; y < w ; y++) {for (int d{} ; d < 4 ; d++) {int nx{x + dx[d]}, ny{y + dy[d]};if (!in(nx, ny)) continue;if (a[x][y] < a[nx][ny]) {g[f(x, y)].push_back(f(nx, ny));deg[f(nx, ny)]++;}}}}std::vector<int> que;std::vector<int> dp(n);for (int i{} ; i < n ; i++) if (deg[i] == 0) {que.push_back(i);dp[i] = 1;}for (int i{} ; i < (int)que.size() ; i++) {int v{que[i]};for (auto x : g[v]) {dp[x] = std::max(dp[x], dp[v] + 1);deg[x]--;if (deg[x] == 0) {que.push_back(x);}}}int ans{*std::max_element(dp.begin(), dp.end())};std::cout << ans << '\n';}