Advertisement
Josif_tepe

Untitled

Mar 23rd, 2023
810
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. int n, m;
  5. int mat[55][55];
  6. int dp[55][55];
  7. pair<int, int> path[55][55];
  8. int rec(int i, int j) {
  9.     if(i == n - 1 and j == m - 1) {
  10.         path[i][j] = make_pair(-1, -1);
  11.         return mat[i][j];
  12.     }
  13.     if(dp[i][j] != -1) {
  14.         return dp[i][j];
  15.     }
  16.     int right_path = 0, down_path = 0;
  17.     if(i + 1 < n) {
  18.         down_path = rec(i + 1, j) + mat[i][j];
  19.     }
  20.     if(j + 1 < m) {
  21.         right_path = rec(i, j + 1) + mat[i][j];
  22.     }
  23.     if(down_path > right_path) {
  24.         path[i][j] = make_pair(i + 1, j);
  25.     }
  26.     else {
  27.         path[i][j] = make_pair(i, j + 1);
  28.     }
  29.     return dp[i][j] = max(down_path, right_path);
  30. }
  31. int main() {
  32.     cin >> n >> m;
  33.     for(int i = 0; i < n; i++) {
  34.         for(int j = 0; j < m; j++) {
  35.             cin >> mat[i][j];
  36.         }
  37.     }
  38.     memset(dp, -1, sizeof dp);
  39.     cout << rec(0, 0) << endl;
  40.     pair<int, int> at;
  41.    
  42.     for(at = make_pair(0, 0); at != make_pair(-1, -1); at = make_pair(path[at.first][at.second].first, path[at.first][at.second].second)) {
  43.         cout << at.first + 1 << " " << at.second +  1<< endl;
  44.     }
  45.     return 0;
  46. }
  47.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement