結果
問題 | No.2639 Longest Increasing Walk |
ユーザー |
![]() |
提出日時 | 2024-02-19 22:40:49 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 2,046 bytes |
コンパイル時間 | 7,940 ms |
コンパイル使用メモリ | 348,592 KB |
実行使用メモリ | 19,896 KB |
最終ジャッジ日時 | 2024-09-29 02:32:42 |
合計ジャッジ時間 | 9,699 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("Ofast,unroll-loops")#include <bits/stdc++.h>#include <atcoder/all>#define rep(i, n) for (int i = 0; i < n; i++)#define per(i, n) for (int i = n - 1; i >= 0; i--)#define ALL(a) a.begin(), a.end()#undef long#define long long long#define ll long#define vec vectorusing namespace std;using mint = atcoder::modint;ostream &operator<<(ostream &os, mint a){return os << a.val();}template <typename T>ostream &operator<<(ostream &os, vector<T> &a){const int n = a.size();rep(i, n){os << a[i];if (i + 1 != n)os << " ";}return os;}template <typename T, size_t n>ostream &operator<<(ostream &os, array<T, n> &a){rep(i, n) os << a[i] << " \n"[i + 1 == n];return os;}template <typename T>istream &operator>>(istream &is, vector<T> &a){for (T &i : a)is >> i;return is;}template <typename T>bool chmin(T &x, T y){if (x > y){x = y;return true;}return false;}template <typename T>bool chmax(T &x, T y){if (x < y){x = y;return true;}return false;}void solve(){int h, w;cin >> h >> w;vec<vec<int>> a(h, vec<int>(w));rep(i, h) rep(j, w) cin >> a[i][j];vec<vec<int>> g(h * w);constexpr int dx[] = {0, 1, 0, -1};constexpr int dy[] = {1, 0, -1, 0};rep(i, h) rep(j, w){rep(k, 4){int nx = i + dx[k];int ny = j + dy[k];if (nx < 0 || nx >= h || ny < 0 || ny >= w)continue;if (a[i][j] < a[nx][ny])g[i * w + j].push_back(nx * w + ny);}}queue<int> q;vec<int> d(h * w);rep(i, h * w) for (int j : g[i]) d[j]++;rep(i, h * w) if (d[i] == 0) q.push(i);vec<int> dp(h * w);while (!q.empty()){const int v = q.front();q.pop();for (int u : g[v]){chmax(dp[u], dp[v] + 1);if (--d[u] == 0)q.push(u);}}cout << *max_element(ALL(dp)) + 1 << endl;}int main(){// srand((unsigned)time(NULL));cin.tie(nullptr);ios::sync_with_stdio(false);// cout << fixed << setprecision(40);int t = 1;// cin >> t;while (t--)solve();return 0;}