Skip to content

Instantly share code, notes, and snippets.

@sarb1208
Created July 15, 2018 12:07
Show Gist options
  • Save sarb1208/7d05abd0f2a180970e68b6a4934a00c6 to your computer and use it in GitHub Desktop.
Save sarb1208/7d05abd0f2a180970e68b6a4934a00c6 to your computer and use it in GitHub Desktop.
C-code for spoj problem named Martian Mining
#include<stdio.h>
int Y[500][500];
int B[500][500];
int max(int a,int b){
if(a>b)
return a;
return b;
}
int fun(int r,int c,int n,int m){
if(r==n||c==m)
return 0;
int i;
int a = 0;
for(i=r;i<n;i++)
a += Y[i][c];
int b = 0;
for(i=c;i<m;i++)
b += B[r][i];
return max(a + fun(r,c+1,n,m),b + fun(r+1,c,n,m));
}
int fun2(int n,int m){
int dp[n+1][m+1];
int i,j,r,c;
for(i=0;i<=n;i++)
dp[i][m] = 0;
for(j=0;j<=m;j++)
dp[n][j] = 0;
int a,b;
for(r=n-1;r>=0;r--){
for(c=m-1;c>=0;c--){
for(i=r,a=0;i<n;i++)
a += Y[i][c];
for(i=c,b=0;i<m;i++)
b += B[r][i];
dp[r][c] = max(a + dp[r][c+1],b + dp[r+1][c]);
}
}
return dp[0][0];
}
int main(){
int n,m;
while(1){
scanf("%d%d",&n,&m);
if(n==0)
break;
int i,j;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
scanf("%d",&Y[i][j]);
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
scanf("%d",&B[i][j]);
}
}
printf("%d\n",fun2(n,m));
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment