Auto comment: topic has been updated by goldenskygiang (previous revision, new revision, compare).

This is a very old problem from codeforces. You can solve it with dynamic programming on diagonals, dp[diag][p1][p2] -> max sum of two paths, where diag — number of diagonal (row_id+col_id), p1 — position of first player on current diagonal, p2 — position of second player on current diagonal.

What are the bounds on N?

So the base idea of the solution is to build the two paths simultaneously and basically looks like this:

  static int solve(int x1, int y1, int x2, int y2) {
    if(x1<=0 || x2<=0 || y1<=0 || y2<=0) return -INF;
    if(x1>M || x2>M || y1>N || y2>N) return -INF;
    int sum = A[y1][x1] + A[y2][x2];
    if(x1==x2 && y1==y2) {
      if(x1==M && y1==N) return A[N][M];
      if(x1!=1 || y1!=1) return -INF;
      sum = A[1][1];
    }
    int best = -INF;
    for(int dx1 = 1, dy1 = 0, tmp; dx1>=0; tmp=dx1, dx1=-dy1, dy1=tmp) {
      for(int dx2 = 1, dy2 = 0; dx2>=0; tmp=dx2, dx2=-dy2, dy2=tmp) {
        best = Math.max(best, solve(x1+dx1, y1+dy1, x2+dx2, y2+dy2));
      }
    }
    return best + sum;
  }

Now you have to apply DP on top of this. Naively doing dp[x1][y1][x2][y2] will obviously lead to $$$O(N^2M^2)$$$. The trick is to realize that since the two paths are not independent, i.e. they move forwards at the same speed, you can do dp[moves][y1][y2] and x1 = moves - y1 x2 = moves - y2. This is $$$O((N+M)N^2)$$$.

(Depending on if you opt for 0-indexing or 1-indexing you may need a +/-1 here and there.)