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.  
  21.         vector<vector<int>> f(n, vector<int>(m, NEG));
  22.         vector<vector<int>> g(n, vector<int>(m, NEG));
  23.  
  24.         f[0][0] = a[0][0];
  25.         for (int i = 0; i < n; i++) {
  26.             for (int j = 0; j < m; j++) {
  27.                 if (i == 0 && j == 0) continue;
  28.                 if (i > 0) f[i][j] = max(f[i][j], f[i-1][j]);
  29.                 if (j > 0) f[i][j] = max(f[i][j], f[i][j-1]);
  30.                 f[i][j] += a[i][j];
  31.             }
  32.         }
  33.  
  34.         g[n-1][m-1] = a[n-1][m-1];
  35.         for (int i = n-1; i >= 0; i--) {
  36.             for (int j = m-1; j >= 0; j--) {
  37.                 if (i == n-1 && j == m-1) continue;
  38.                 if (i+1 < n) g[i][j] = max(g[i][j], g[i+1][j]);
  39.                 if (j+1 < m) g[i][j] = max(g[i][j], g[i][j+1]);
  40.                 g[i][j] += a[i][j];
  41.             }
  42.         }
  43.  
  44.         int BEST = f[n-1][m-1];
  45.         int ans = BEST;
  46.  
  47.  
  48.         for (int x = 0; x < n; x++) {
  49.             for (int y = 0; y < m; y++) {
  50.                 if (f[x][y] + g[x][y] - a[x][y] != BEST) continue;
  51.  
  52.                 a[x][y] = -a[x][y]; 
  53.  
  54.                 vector<vector<int>> dp(n, vector<int>(m, NEG));
  55.                 dp[0][0] = a[0][0];
  56.  
  57.                 for (int i = 0; i < n; i++) {
  58.                     for (int j = 0; j < m; j++) {
  59.                         if (i == 0 && j == 0) continue;
  60.                         if (i > 0) dp[i][j] = max(dp[i][j], dp[i-1][j]);
  61.                         if (j > 0) dp[i][j] = max(dp[i][j], dp[i][j-1]);
  62.                         dp[i][j] += a[i][j];
  63.                     }
  64.                 }
  65.  
  66.                 ans = min(ans, dp[n-1][m-1]);
  67.                 a[x][y] = -a[x][y]; 
  68.             }
  69.         }
  70.  
  71.         cout << ans << '\n';
  72.     }
  73.     return 0;
  74. }
  75.  
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 
3
-5
https://ideone.com/qLjK1t
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!