n3v07_Tk's blog

By n3v07_Tk, history, 4 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it