Saleh127

Timus 1146

Jun 3rd, 2021
212
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5.  
  6. ll a[200][200];
  7.  
  8. ll submatrixsum(ll x,ll y,ll n)
  9. {
  10.  
  11. ll sum[200];
  12.  
  13. memset(sum,0,sizeof sum);
  14.  
  15. for(ll i=0;i<n;i++)
  16. {
  17. for(ll j=x;j<=y;j++)
  18. {
  19. sum[i]+= a[i][j];
  20. }
  21. }
  22.  
  23. ll ans=INT_MIN,l=0;
  24.  
  25. for(ll i=0;i<n;i++)
  26. {
  27. l+=sum[i];
  28.  
  29. ans=max(ans,l);
  30.  
  31. if(l<0) l=0;
  32. }
  33.  
  34. return ans;
  35. }
  36.  
  37. int main()
  38. {
  39. ios_base::sync_with_stdio(0);
  40. cin.tie(0);cout.tie(0);
  41.  
  42.  
  43. ll n,m,i,j,k,l,ans=INT_MIN;
  44.  
  45. cin>>n;
  46.  
  47. for(i=0;i<n;i++)
  48. {
  49. for(j=0;j<n;j++)
  50. {
  51. cin>>a[i][j];
  52. }
  53. }
  54.  
  55.  
  56. for(i=0;i<n;i++)
  57. {
  58. for(j=i;j<n;j++)
  59. {
  60. ans=max(ans,submatrixsum(i,j,n));
  61. }
  62. }
  63.  
  64. cout<<ans<<endl;
  65.  
  66. return 0;
  67. }
  68.  
Advertisement
Add Comment
Please, Sign In to add comment