Advertisement
Mirbek

D. Горнолыжная база

Jan 26th, 2022
810
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 55;
  6.  
  7. int n, m;
  8. int h[N][N], dp[N][N];
  9. vector < pair <int, pair <int, int> > > vec;
  10.  
  11. int main(){
  12.     cin >> n >> m;
  13.  
  14.     for (int i = 1; i <= n; i++) {
  15.         for (int j = 1; j <= m; j++) {
  16.             cin >> h[i][j];
  17.             vec.push_back({h[i][j], {i, j}});
  18.         }
  19.     }
  20.  
  21.     sort(vec.rbegin(), vec.rend());
  22.  
  23.     for (auto v : vec) {
  24.         int i = v.second.first;
  25.         int j = v.second.second;
  26.         if (i - 1 >= 1 && h[i][j] > h[i - 1][j]) {
  27.             dp[i - 1][j] = max(dp[i - 1][j], dp[i][j] + 1);
  28.         }
  29.         if (i + 1 <= n && h[i][j] > h[i + 1][j]) {
  30.             dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1);
  31.         }
  32.         if (j - 1 >= 1 && h[i][j] > h[i][j - 1]) {
  33.             dp[i][j - 1] = max(dp[i][j - 1], dp[i][j] + 1);
  34.         }
  35.         if (j + 1 <= m && h[i][j] > h[i][j + 1]) {
  36.             dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + 1);
  37.         }
  38.     }
  39.  
  40.     cout << dp[1][1] << endl;
  41. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement