SHARE
TWEET

lightoj - 1036 - A Refining Company

jakaria_hossain Sep 7th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int mn=555;
  4. int dp[mn][mn];
  5.  
  6. #define fast()(ios_base::sync_with_stdio(0),cin.tie(NULL));
  7. int go(vector<vector<int> > &a, vector<vector<int> > &b,int i, int j)
  8. {
  9.     if(i<0 || j<0)return 0;
  10.     if(dp[i][j]!=-1)return dp[i][j];
  11.     return dp[i][j]=max(go(a,b,i-1,j)+a[i][j], go(a,b,i,j-1)+b[i][j]);
  12. }
  13.  
  14. void solve()
  15. {
  16.     int n,m;
  17.     cin>>n>>m;
  18.     vector<vector<int> >a(n,vector<int>(m)),b(n,vector<int>(m));
  19.     for(int i=0;i<n;i++)
  20.     {
  21.         for(int j=0;j<m;j++)
  22.         {
  23.             cin>>a[i][j];
  24.             if(j)
  25.                 a[i][j]+=a[i][j-1];
  26.         }
  27.     }
  28.     for(int i=0;i<n;i++)
  29.     {
  30.         for(int j=0;j<m;j++)
  31.         {
  32.             cin>>b[i][j];
  33.             if(i)
  34.                 b[i][j]+=b[i-1][j];
  35.         }
  36.     }
  37.     memset(dp,-1,sizeof dp);
  38.     printf("%d\n",go(a,b,n-1,m-1));
  39. }
  40. int main()
  41. {
  42.     fast();
  43.     int t,c;
  44.     cin>>t;
  45.     for(c=1;c<=t;c++)
  46.     {
  47.         printf("Case %d: ",c);
  48.         solve();
  49.     }
  50. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top