There is a rectangular field with two types of resources viz, resource A and resource B. At each cell in the field, both of the resources can be present. There are two types of factory which can collect resource A and B. If resource A is collected in a factory then resource B is lost and vice versa. Now, these two factories are located perpendicular to each other i.e the factory collecting resource A is at the top ( north) of the rectangular field and the factory collecting resource B is to the left ( west) of the rectangular field. The resources have to be brought to the factory on a straight path without taking any turns. This implies that if there is any south-north conveyer belt in the cell, but the cell north of it contains an east-west conveyer belt, then all resources transported on the south-north conveyer belt will be lost.
You have to design a conveyer belt system that maximizes the total amount of minerals mined, i.e the sum of the amount of resource A transported to the top and the sum of the amount of resource B transported to the left. You are given a 2-D matrix A and B of the same size denoting the amount of resource of the corresponding type in that cell.
Since the answer can be large, return it modulo 109 + 7.
Problem Constraints
1 <= |A| = |B| <= 103
1 <= |A[0]| = |B[0]| <=103
0 <= A[i][j], B[i][j] <= 109
Input Format
The first line contains a matrix that specifies the availability of the resource A in each of the cells.
The second line contains a matrix that specifies the availability of the resource B in each of the cells.
Output Format
Return a single integer which specifies the maximum amount of resources that can be processed by the factories.
Example Input
Input 1:
A = [
[7, 8, 9]
[4, 5, 6]
[1, 2, 3]
]
B = [
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
]
Input 2:
A = [
[1, 0, 1]
]
B = [
[2, 1, 0]
]
Example Output
Output 1:
63
Output 2:
4
Example Explanation
Explanation 1:
The first row can be sent to the top to collect resource A. The rest two rows will be sent to the left to collect resource B.
Explanation 2:
The first two columns can be sent to the left. The third column will be sent to the top.Total resource collected - 2 + 1 + 1 = 4
Code:
int r,c,a[1005][1005],b[1005][1005];long long dp[1005],mx[1005];int Solution::solve(vector<vector<int> > &A, vector<vector<int> > &B) {long long ans=0,s=0;r=A.size();c=A[0].size();for(int i=0;i<r;i++){for(int j=0;j<c;j++){a[i][j]=A[i][j];ans+=a[i][j];}}for(int i=0;i<r;i++){for(int j=0;j<c;j++){b[i][j]=B[i][j];b[i][j]-=a[i][j];}}dp[0]=0;mx[0]=0;for(int i=1;i<=c;i++){s+=b[0][i-1];dp[i]=s;mx[i]=max(mx[i-1],dp[i]);}for(int i=1;i<r;i++){dp[0]=mx[0];s=0;for(int j=1;j<=c;j++){s+=b[i][j-1];dp[j]=s+mx[j];}for(int j=1;j<=c;j++)mx[j]=max(mx[j-1],dp[j]);}return (ans+mx[c])%1000000007;}
ConversionConversion EmoticonEmoticon