結果
問題 | No.2639 Longest Increasing Walk |
ユーザー |
![]() |
提出日時 | 2024-02-19 21:32:12 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 1,207 bytes |
コンパイル時間 | 4,910 ms |
コンパイル使用メモリ | 313,940 KB |
実行使用メモリ | 7,376 KB |
最終ジャッジ日時 | 2024-09-29 01:28:32 |
合計ジャッジ時間 | 6,827 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <atcoder/all>#include <bits/stdc++.h>using ll = long long;using ull = unsigned long long;#define rep(i, n) for(int i = 0; i < (int)(n); i++)#define REP(i, m, n) for(int i = (int)(m); i < (int)(n); i++)using namespace std;using namespace atcoder;using mint = modint998244353;const int inf = 1000000007;const ll longinf = 1ll << 60;int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int h, w;cin >> h >> w;vector<vector<int>> a(h, vector<int>(w, 0));rep(i, h) rep(j, w) cin >> a[i][j];vector<pair<int, int>> ord;rep(i, h) rep(j, w) ord.push_back({i, j});sort(ord.begin(), ord.end(), [&](pair<int, int> x, pair<int, int> y) {return a[x.first][x.second] < a[y.first][y.second];});vector dp(h, vector<int>(w, 1));vector<int> d = {1, 0, -1, 0, 1};int ans = 0;for(auto [x, y] : ord) {rep(i, 4) {int nx = x + d[i], ny = y + d[i + 1];if(0 <= nx && nx < h && 0 <= ny && ny < w && a[nx][ny] < a[x][y]) {dp[x][y] = max(dp[nx][ny] + 1, dp[x][y]);}}ans = max(ans, dp[x][y]);}cout << ans << endl;return 0;}