While trying to solve a problem of dp on SPOJ I am facing some issues. I have already implemented it recursively and it worked fine but the iterative version of the code is passing the pretests and failing system tests.
It would be a great help if someone could either debug my code or give me a test case on which my below code fails.
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n , m;
cin >> n >> m;
long long a[ n + 1 ][ m + 1 ] , b[ n + 1 ][ m + 1 ];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> b[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[ i ][ j ];
}
}
long long dp[ n + 1 ][ m + 1 ] , sum[ n + 1 ][ m + 1 ][ 2 ];
memset( dp, 0, sizeof(dp));
memset( sum, 0, sizeof(sum));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
sum[ i ][ j ][ 0 ] += sum[ i ][ j - 1 ][ 0 ] + b[ i ][ j ]; // row sum
sum[ i ][ j ][ 1 ] += sum[ i - 1 ][ j ][ 1 ] + a[ i ][ j ]; // col sum
long long val = dp[ i - 1 ][ j ] + sum[ i ][ j ][ 0 ];
long long val1= dp[ i ][ j - 1 ] + sum[ i ][ j ][ 1 ];
dp[ i ][ j ] =max( val ,val1);
}
}
cout << dp[ n ][ m ];
}
You forgot the input format