ohwhatalovelyday

Untitled

Mar 27th, 2021
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define FASTER() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  4. #define ff first
  5. #define ss second
  6. #define pb push_back
  7. #define all(a) a.begin(), a.end()
  8. #define dbg(x) cerr<<" "<<#x<<" "<<x<<endl
  9. #define int long long
  10.  
  11. typedef long long ll;
  12.  
  13. using namespace std;
  14.  
  15. signed main() {
  16.     FASTER();
  17.     int n, m;
  18.     cin >> n >> m;
  19.     vector <vector <int>> mt(n, vector <int>(m));
  20.     for(auto &a : mt) {
  21.         for(auto &i : a) {
  22.             cin >> i;
  23.         }
  24.     }
  25.     vector <vector <int>> dp1(n, vector <int>(m)), dp2(n, vector <int>(m));
  26.     dp1[0][0] = mt[0][0];
  27.     dp2[n - 1][m - 1] = mt[n - 1][m - 1];
  28.     for(int i = 1; i < n; i++) {
  29.         dp1[i][0] = dp1[i - 1][0] + mt[i][0];
  30.         dp2[n - i - 1][m - 1] = dp2[n - i][m - 1] + mt[n - i - 1][m - 1];
  31.     }
  32.     for(int j = 1; j < m; j++) {
  33.         dp1[0][j] = dp1[0][j - 1] + mt[0][j];
  34.         dp2[n - 1][m - j - 1] = dp2[n - 1][m - j] + mt[n - 1][m - j - 1];
  35.     }
  36.     for(int i = 1; i < n; i++) {
  37.         for(int j = 1; j < m; j++) {
  38.             dp1[i][j] = max(dp1[i - 1][j], dp1[i][j - 1]) + mt[i][j];
  39.         }
  40.     }
  41.     for(int i = n - 2; i >= 0; i--) {
  42.         for(int j = m - 2; j >= 0; j--) {
  43.             dp2[i][j] = max(dp2[i + 1][j], dp2[i][j + 1]) + mt[i][j];
  44.         }
  45.     }
  46.     vector <pair <int, int>> sums;
  47.     for(int ni = 1; ni < n; ni++) {
  48.         int i = ni, j = 0;
  49.         int mx1 = 0, mx2 = 0;
  50.         while(i >= 0) {
  51.             int cur = dp1[i][j] + dp2[i][j] - mt[i][j];
  52.             if(cur > mx1) {
  53.                 mx2 = mx1;
  54.                 mx1 = cur;
  55.             } else if(cur > mx2) {
  56.                 mx2 = cur;
  57.             }
  58.             i--;
  59.             j++;
  60.         }
  61.         sums.pb({mx2, mx1});
  62.     }
  63.     for(int nj = 1; nj < m - 1; nj++) {
  64.         int j = nj, i = n - 1;
  65.         int mx1 = 0, mx2 = 0;
  66.         while(i >= 0) {
  67.             if(j >= m) break;
  68.             int cur = dp1[i][j] + dp2[i][j] - mt[i][j];
  69.             if(cur > mx1) {
  70.                 mx2 = mx1;
  71.                 mx1 = cur;
  72.             } else if(cur > mx2) {
  73.                 mx2 = cur;
  74.             }
  75.             i--;
  76.             j++;
  77.         }
  78.         sums.pb({mx2, mx1});
  79.     }
  80.     sort(all(sums));
  81. //    for(auto a : sums) cout << a.ff << " " << a.ss << endl;
  82.     cout << sums[0].ff;
  83. }
  84.  
Advertisement
Add Comment
Please, Sign In to add comment