rembocoder

Untitled

May 14th, 2023
670
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define int int64_t
  4.  
  5. using namespace std;
  6.  
  7. void relax(int& a, int b) {
  8.     a = max(a, b);
  9. }
  10.  
  11. int32_t main() {
  12.     ios_base::sync_with_stdio(false);
  13.     int n, m;
  14.     cin >> n >> m;
  15.     vector<vector<int>> a(n, vector<int>(m));
  16.     for (int i = 0; i < n; i++) {
  17.         for (int j = 0; j < m; j++) {
  18.             cin >> a[i][j];
  19.         }
  20.     }
  21.     vector<vector<int>> dp(n, vector<int>(m, -2e18));
  22.     dp[0][0] = a[0][0];
  23.     for (int i = 0; i < n; i++) {
  24.         for (int j = 0; j < m; j++) {
  25.             if (i == 0 && j == 0) {
  26.                 continue;
  27.             }
  28.             if (i) {
  29.                 relax(dp[i][j], dp[i - 1][j] + a[i][j]);
  30.             }
  31.             if (j) {
  32.                 relax(dp[i][j], dp[i][j - 1] + a[i][j]);
  33.             }
  34.         }
  35.     }
  36.     cout << dp[n - 1][m - 1] << '\n';
  37. }
  38.  
Advertisement
Add Comment
Please, Sign In to add comment