fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int NEG = -4e18;
  5.  
  6. signed main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int t; cin >> t;
  11.     while (t--) {
  12.         int n, m;
  13.         cin >> n >> m;
  14.  
  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.         vector<vector<int>> f(n, vector<int>(m, NEG));
  21.         vector<vector<int>> g(n, vector<int>(m, NEG));
  22.  
  23.         f[0][0] = a[0][0];
  24.         for (int i = 0; i < n; i++) {
  25.             for (int j = 0; j < m; j++) {
  26.                 if (i == 0 && j == 0) continue;
  27.                 if (i > 0) f[i][j] = max(f[i][j], f[i-1][j]);
  28.                 if (j > 0) f[i][j] = max(f[i][j], f[i][j-1]);
  29.                 f[i][j] += a[i][j];
  30.             }
  31.         }
  32.  
  33.         g[n-1][m-1] = a[n-1][m-1];
  34.         for (int i = n-1; i >= 0; i--) {
  35.             for (int j = m-1; j >= 0; j--) {
  36.                 if (i == n-1 && j == m-1) continue;
  37.                 if (i+1 < n) g[i][j] = max(g[i][j], g[i+1][j]);
  38.                 if (j+1 < m) g[i][j] = max(g[i][j], g[i][j+1]);
  39.                 g[i][j] += a[i][j];
  40.             }
  41.         }
  42.  
  43.         int BEST = f[n-1][m-1];
  44.         int ans = BEST;
  45.  
  46.         for (int i = 0; i < n; i++) {
  47.             for (int j = 0; j < m; j++) {
  48.                 if (f[i][j] + g[i][j] - a[i][j] == BEST) {
  49.                     ans = min(ans, BEST - 2 * a[i][j]);
  50.                 }
  51.             }
  52.         }
  53.  
  54.         cout << ans << '\n';
  55.     }
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
2
3 3
1 -2 3
4 -5 2
1 6 -1
2 4
-1 -1 -1 1
-1 -1 -1 -1
stdout
copy 
-1
-5
https://ideone.com/1EK6E7
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!