結果
問題 | No.2639 Longest Increasing Walk |
ユーザー |
|
提出日時 | 2024-02-19 22:11:17 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 122 ms / 2,000 ms |
コード長 | 1,723 bytes |
コンパイル時間 | 1,076 ms |
コンパイル使用メモリ | 100,772 KB |
実行使用メモリ | 8,448 KB |
最終ジャッジ日時 | 2024-09-29 02:05:31 |
合計ジャッジ時間 | 3,539 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream>#include <vector>#include <queue>using namespace std;int main () {int H, W; cin >> H >> W;vector<vector<int>> A(H, vector<int>(W));for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> A[i][j];// DAGになるやつ -> 最長経路問題はdpで求まるauto is_in = [&](int i, int j) {return 0 <= i && i < H && 0 <= j && j < W;};vector<vector<int>> indeg(H, vector<int>(W));const vector<pair<int, int>> dxy = {make_pair(0, 1),make_pair(1, 0),make_pair(0, -1),make_pair(-1, 0),};for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {for (auto& d : dxy) {int y = i + d.first;int x = j + d.second;if (!is_in(y, x)) continue;if (A[i][j] < A[y][x]) indeg[y][x]++;}}vector<vector<int>> vis(H, vector<int>(W, -1));queue<pair<int, int>> Q;for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {if (indeg[i][j] == 0) Q.push(make_pair(i, j));}while (!Q.empty()) {auto pos = Q.front(); Q.pop();int i = pos.first;int j = pos.second;if (vis[i][j] == -1) vis[i][j] = 0;for (auto& d : dxy) {int y = i + d.first;int x = j + d.second;if (!is_in(y, x)) continue;if (A[y][x] <= A[i][j]) continue;vis[y][x] = max(vis[y][x], vis[i][j] + 1);indeg[y][x]--;if (indeg[y][x] == 0) Q.push(make_pair(y, x));}}int ans = 0;for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) ans = max(ans, vis[i][j] + 1);cout << ans << "\n";}