結果
問題 | No.2639 Longest Increasing Walk |
ユーザー |
|
提出日時 | 2024-02-19 21:44:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 938 bytes |
コンパイル時間 | 2,160 ms |
コンパイル使用メモリ | 209,508 KB |
最終ジャッジ日時 | 2025-02-19 16:48:03 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int H,W; cin >> H >> W;vector<tuple<int,int,int>> X;vector<vector<int>> A(H,vector<int>(W));for(int i=0; i<H; i++) for(int k=0; k<W; k++){int a; cin >> a;A.at(i).at(k) = a;X.push_back({a,i,k});}sort(X.rbegin(),X.rend());vector dist(H,vector<int>(W));vector<int> dx = {-1,0,1,0},dy = {0,1,0,-1};for(auto [a,x,y] : X){int now = dist.at(x).at(y);for(int i=0; i<4; i++){int nx = x+dx.at(i),ny = y+dy.at(i);if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;if(A.at(nx).at(ny) >= a) continue;dist.at(nx).at(ny) = max(dist.at(nx).at(ny),now+1);}}int answer = 0;for(auto &h : dist) for(auto &w : h) answer = max(answer,w);cout << answer+1 << endl;}