Advertisement
Saleh127

SPOJ BYTESM2 / DP

Nov 6th, 2021
757
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-06-20.29.24
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. ll a[1005][1005];
  13. ll dp[200][200];
  14. ll n,m;
  15.  
  16.  
  17. int main()
  18. {
  19.    ios_base::sync_with_stdio(0);
  20.    cin.tie(0);cout.tie(0);
  21.  
  22.    test
  23.    {
  24.         ll i,j,k,l,h,ans=0;
  25.  
  26.         cin>>n>>m;
  27.  
  28.         memset(dp,0,sizeof dp);
  29.  
  30.         for(i=0;i<n;i++)
  31.         {
  32.              for(j=0;j<m;j++)
  33.              {
  34.                   cin>>a[i][j];
  35.                   dp[i][j]=a[i][j];
  36.              }
  37.         }
  38.  
  39.         for(i=0;i<n;i++)
  40.         {
  41.              for(j=0;j<m;j++)
  42.              {
  43.                   k=l=h=0;
  44.  
  45.                   if(i-1>=0 && j-1>=0) k=dp[i-1][j-1];
  46.                   if(i-1>=0) l=dp[i-1][j];
  47.                   if(i-1>=0 && j+1<m) h=dp[i-1][j+1];
  48.  
  49.                   dp[i][j]+=max({k,l,h});
  50.              }
  51.  
  52.         }
  53.  
  54.         for(i=0;i<n;i++)
  55.         {
  56.              for(j=0;j<m;j++)
  57.              {
  58.                  ans=max(ans,dp[i][j]);
  59.              }
  60.         }
  61.  
  62.         cout<<ans<<nl;
  63.    }
  64.  
  65.    get_lost_idiot;
  66. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement