Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define FASTER() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
- #define ff first
- #define ss second
- #define pb push_back
- #define all(a) a.begin(), a.end()
- #define dbg(x) cerr<<" "<<#x<<" "<<x<<endl
- #define int long long
- typedef long long ll;
- using namespace std;
- signed main() {
- FASTER();
- int n, m;
- cin >> n >> m;
- vector <vector <int>> mt(n, vector <int>(m));
- for(auto &a : mt) {
- for(auto &i : a) {
- cin >> i;
- }
- }
- vector <vector <int>> dp1(n, vector <int>(m)), dp2(n, vector <int>(m));
- dp1[0][0] = mt[0][0];
- dp2[n - 1][m - 1] = mt[n - 1][m - 1];
- for(int i = 1; i < n; i++) {
- dp1[i][0] = dp1[i - 1][0] + mt[i][0];
- dp2[n - i - 1][m - 1] = dp2[n - i][m - 1] + mt[n - i - 1][m - 1];
- }
- for(int j = 1; j < m; j++) {
- dp1[0][j] = dp1[0][j - 1] + mt[0][j];
- dp2[n - 1][m - j - 1] = dp2[n - 1][m - j] + mt[n - 1][m - j - 1];
- }
- for(int i = 1; i < n; i++) {
- for(int j = 1; j < m; j++) {
- dp1[i][j] = max(dp1[i - 1][j], dp1[i][j - 1]) + mt[i][j];
- }
- }
- for(int i = n - 2; i >= 0; i--) {
- for(int j = m - 2; j >= 0; j--) {
- dp2[i][j] = max(dp2[i + 1][j], dp2[i][j + 1]) + mt[i][j];
- }
- }
- vector <pair <int, int>> sums;
- for(int ni = 1; ni < n; ni++) {
- int i = ni, j = 0;
- int mx1 = 0, mx2 = 0;
- while(i >= 0) {
- int cur = dp1[i][j] + dp2[i][j] - mt[i][j];
- if(cur > mx1) {
- mx2 = mx1;
- mx1 = cur;
- } else if(cur > mx2) {
- mx2 = cur;
- }
- i--;
- j++;
- }
- sums.pb({mx2, mx1});
- }
- for(int nj = 1; nj < m - 1; nj++) {
- int j = nj, i = n - 1;
- int mx1 = 0, mx2 = 0;
- while(i >= 0) {
- if(j >= m) break;
- int cur = dp1[i][j] + dp2[i][j] - mt[i][j];
- if(cur > mx1) {
- mx2 = mx1;
- mx1 = cur;
- } else if(cur > mx2) {
- mx2 = cur;
- }
- i--;
- j++;
- }
- sums.pb({mx2, mx1});
- }
- sort(all(sums));
- // for(auto a : sums) cout << a.ff << " " << a.ss << endl;
- cout << sums[0].ff;
- }
Advertisement
Add Comment
Please, Sign In to add comment