Advertisement
Josif_tepe

Untitled

Dec 8th, 2021
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <bits/stdc++.h>  
  2.  
  3. using namespace std;  
  4.  
  5. int main()  
  6. {  
  7.     int n, m, a[50][50], dp[50][50] = {};  
  8.     cin >> n >> m;  
  9.     for (int i = 0; i < n; i++)  
  10.         for (int j = 0; j < m; j++)  
  11.             cin >> a[i][j];  
  12.     dp[0][0] = a[0][0];  
  13.     for (int i = 1; i < n; i++)  
  14.         dp[0][i] = a[0][i] + dp[0][i-1];  
  15.     for (int i = 1; i < m; i++)  
  16.         dp[i][0] = a[i][0] + dp[i-1][0];  
  17.     for (int i = 1; i < n; i++)  
  18.         for (int j = 1; j < m; j++)  
  19.             dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j-1]);  
  20.     cout << dp[n-1][m-1] << endl;  
  21.  
  22.     vector<pair<int, int> > result;  
  23.  
  24.     int i = m - 1, j = n - 1;  
  25.     result.push_back({i+1, j+1});  
  26.  
  27.     while (i != 0 || j != 0) {  
  28.  
  29.         if (i > 0 && dp[i][j] == dp[i-1][j] + a[i][j]) {  
  30.             i--;  
  31.         } else {  
  32.             j--;  
  33.         }  
  34.  
  35.         result.push_back({i+1, j+1});  
  36.     }  
  37.  
  38.     reverse(result.begin(), result.end());  
  39.     for(int i=0; i<result.size(); i++){
  40.     cout << result[i].first << " " << result[i].second << endl;  
  41.     }  
  42.  
  43.  
  44.     return 0;  
  45. }  
  46.  
  47.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement