burnmanhootam.cpp

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7; 
// usaremos o INF como um indicador que ainda não calculamos
// o estado. Note que não podemos usar artificios como -1
// pois a recursão aceita valores negativos

int A[212][212], pref[212][212];
int H[212][212], V[212][212];
int n, m;
int dp_ida[212][212];
int dp_volta[212][212];

int fazdp_ida(int x, int y){
	//verificamos se já calculamos o estado atual, ou se essa é a base da recursão
	if(x == n && y == m) return 0;
	if(dp_ida[x][y] != INF) return dp_ida[x][y];

	//se estamos na ultima linha ou coluna, podemos apenas ir para a direita ou para baixo, respectivamente.
	if(x == n) return dp_ida[x][y] = fazdp_ida(x, y + 1) - H[x][y];
	if(y == m) return dp_ida[x][y] = fazdp_ida(x+ 1 , y) - V[x][y];

	//calculamos os dois valores possíveis para essa recursão, indo pa a direita
	//e adicionando uma nova coluna, ou descemos para a próxima linha
	int ans1, ans2;
	ans1 = fazdp_ida(x, y + 1) + pref[x][y] - H[x][y];
	ans2 = fazdp_ida(x + 1, y) - V[x][y];;
	
	return dp_ida[x][y] = max(ans1, ans2);
}

int fazdp_volta(int x, int y){
	//verificamos se já calculamos o estado atual, ou se essa é a base da recursão
	if(x == n && y == m) return 0;
	if(dp_volta[x][y] != INF) return dp_volta[x][y];
	//se estamos na ultima linha ou coluna, podemos apenas ir para a direita ou para baixo, respectivamente.
	if(x == n) return dp_volta[x][y] = fazdp_volta(x, y + 1) - H[x][y];
	if(y == m) return dp_volta[x][y] = fazdp_volta(x + 1, y) - V[x][y];

	//calculamos os dois valores possíveis para essa recursão, indo pa a direita
	//e adicionando uma nova coluna, ou descemos para a próxima linha
	int ans1 = fazdp_volta(x, y + 1) - pref[x][y] - H[x][y];
	int ans2 = fazdp_volta(x + 1, y) - V[x][y];

	return dp_volta[x][y] = max(ans1, ans2);
}



int main(){
	//inicializamos as DPs como infinita, pra mostrar que ainda não lemos.
	scanf("%d %d", &n, &m);
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= m; j++)
			dp_ida[i][j] = INF, dp_volta[i][j] = INF;
	
	//lemos a entrada
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			scanf("%d", &A[i][j]);

	for(int i = 0; i <= n; i++)
		for(int j = 0; j < m; j++ )
			scanf("%d", &H[i][j]);
	for(int i = 0; i <= m; i++)
		for(int j = 0; j < n; j++)
			scanf("%d", &V[j][i]);

	//pré-calculamos as somas de prefixo
	for(int i = 0; i < m; i++)
		for(int j = n - 1; j >= 0; j--)
			pref[j][i] = pref[j+1][i] + A[j][i];

	int ans = fazdp_ida(0, 0) + fazdp_volta(0, 0); //note que aqui somamos a volta, pois essa já é negativa
												
	printf("%d\n", ans);

}