Help in bebugging a DP solution

Revision en1, by n3v07_Tk, 2021-01-27 21:14:49

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.

PROBLEM link

#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 ];	
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English n3v07_Tk 2021-01-27 21:14:49 1365 Initial revision (published)