Appleby Contest '19 P5 - Matrix Operation

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 2e18; //❄️
    7struct cell {
    8    ll val;
    9    int r, c;
    10    bool operator<(const cell &a) const {
    11        return val < a.val;
    12    }
    13};
    14int main() {
    15    ios::sync_with_stdio(0); cin.tie(0); 
    16    int n; cin >> n;
    17    vector<vector<ll>> v(n, vector<ll>(n));
    18    vector<cell> cells;
    19    for (int i = 0; i < n; i++) {
    20        for (int j = 0; j < n; j++) {
    21            cin >> v[i][j];
    22            cells.push_back({v[i][j], i, j});
    23        }
    24    }
    25    sort(cells.begin(), cells.end());
    26    vector<vector<int>> dp(n, vector<int>(n));
    27    vector<vector<int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    28    int ans = 0;
    29    for (int i = 0; i < cells.size(); i++) {
    30        int r = cells[i].r, c = cells[i].c;
    31        for (auto &d : dir) {
    32            int nr = r + d[0];
    33            int nc = c + d[1];
    34            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
    35                if (v[nr][nc] < v[r][c]) {
    36                    dp[r][c] = max(dp[nr][nc] + 1, dp[r][c]);
    37                }
    38            }
    39        }
    40        ans = max(ans, dp[r][c]);
    41    }
    42    cout << ans << '\n';
    43    return 0;
    44}
    45//recursion implementation
    46/*
    47#include <bits/stdc++.h>
    48using namespace std;
    49int n, g[1502][1502], dp[1502][1502], ans = 0;
    50int dir[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    51int f(int r, int c) {
    52    if(dp[r][c]) return dp[r][c];
    53    dp[r][c] = 1;
    54    for(int k=0; k<4; k++) {
    55        int nr = r + dir[k][0], nc = c + dir[k][1];
    56        if(g[r][c] < g[nr][nc]) dp[r][c] = max(dp[r][c], f(nr, nc) + 1);
    57    }
    58    return dp[r][c];
    59}
    60int main(){
    61    cin >> n;
    62    for(int i=1; i<=n; i++){
    63        for(int j=1; j<=n; j++)
    64            cin >> g[i][j];
    65    }
    66    for(int i=1; i<=n; i++) {
    67        for(int j=1; j<=n; j++)
    68            ans = max(ans, f(i, j));
    69    }
    70    cout << ans - 1 << endl;
    71}
    72*/