結果
問題 | No.2639 Longest Increasing Walk |
ユーザー | 遭難者 |
提出日時 | 2024-02-19 22:40:49 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 2,046 bytes |
コンパイル時間 | 8,463 ms |
コンパイル使用メモリ | 348,964 KB |
実行使用メモリ | 20,032 KB |
最終ジャッジ日時 | 2024-02-19 22:41:00 |
合計ジャッジ時間 | 8,962 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 43 ms
13,248 KB |
testcase_05 | AC | 61 ms
20,032 KB |
testcase_06 | AC | 63 ms
19,668 KB |
testcase_07 | AC | 72 ms
19,636 KB |
testcase_08 | AC | 64 ms
19,852 KB |
testcase_09 | AC | 72 ms
19,876 KB |
testcase_10 | AC | 43 ms
12,032 KB |
testcase_11 | AC | 39 ms
11,136 KB |
testcase_12 | AC | 8 ms
6,676 KB |
testcase_13 | AC | 45 ms
12,608 KB |
testcase_14 | AC | 28 ms
8,704 KB |
testcase_15 | AC | 3 ms
6,676 KB |
testcase_16 | AC | 3 ms
6,676 KB |
testcase_17 | AC | 30 ms
8,704 KB |
testcase_18 | AC | 33 ms
9,728 KB |
testcase_19 | AC | 11 ms
6,676 KB |
testcase_20 | AC | 21 ms
7,168 KB |
testcase_21 | AC | 46 ms
11,008 KB |
testcase_22 | AC | 15 ms
6,676 KB |
testcase_23 | AC | 2 ms
6,676 KB |
testcase_24 | AC | 2 ms
6,676 KB |
testcase_25 | AC | 3 ms
6,676 KB |
testcase_26 | AC | 2 ms
6,676 KB |
testcase_27 | AC | 3 ms
6,676 KB |
testcase_28 | AC | 2 ms
6,676 KB |
testcase_29 | AC | 3 ms
6,676 KB |
testcase_30 | AC | 2 ms
6,676 KB |
testcase_31 | AC | 3 ms
6,676 KB |
testcase_32 | AC | 2 ms
6,676 KB |
ソースコード
#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 vector using 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; }