daily pastebin goal
37%
SHARE
TWEET

maximum sum sub-rectangle

Wazedrifat Jan 20th, 2018 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //wazed rifat
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define INT int
  7. #define MAX 1<<64
  8. #define MAX3(A,B,C) max(A , max(B , C) )
  9. #define PI 2.0*acos(0.0)
  10. #define PII pair<INT,INT>
  11. #define READ freopen("input2.txt","r",stdin);
  12. #define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  13. #define EPS 1e-9
  14. #define DIS(x1,y1,x2,y2) sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) )
  15.  
  16. INT i,j,n,m,test,sum,cnt,t,ps,l,k,f,maxx,a[101][101],dp[101];
  17.  
  18. INT MS( )
  19. {
  20.     INT maxi=INT_MIN,s=0;
  21.    
  22.     for(int ii=0 ; ii<n ; ii++)
  23.     {
  24.         maxi=max(maxi,s+dp[ii]);
  25.         s=max(0,s+dp[ii]);
  26.     }
  27.    
  28.     return maxi;
  29. }
  30.  
  31. int main(   )
  32. {
  33. //  READ
  34.    
  35.     cin>>n;
  36.    
  37.     for(i=0 ; i<n ; i++)
  38.     for(j=0 ; j<n ; j++)
  39.     cin>>a[i][j];
  40.    
  41.     for(i=0,maxx=INT_MIN ; i<n ; i++)
  42.     {
  43.     //  memset(dp,0,sizeof dp);
  44.         for(j=0 ; j<n ; j++)    dp[j]=0;
  45.        
  46.         for(k=i ; k<n ; k++)
  47.         {
  48.             for(j=0 ; j<n ; j++)
  49.             dp[j]+=a[k][j];
  50.            
  51.             maxx=max(maxx,MS());
  52.            
  53.         //  for(int ii=0 ; ii<n ; ii++) cout<<dp[ii]<<" ";
  54.         //  cout<<endl<<"i="<<i<<"  k="<<k<<"  MS="<<MS()<<endl;
  55.         }
  56.     }
  57.     //co\ut<<endl;
  58.     cout<<maxx;
  59. }
RAW Paste Data
Top