Saleh127

UVA 108 / DP - Maximum Interval Sum 2D

Dec 4th, 2021
969
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-12-04-09.26.35
  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. int main()
  13. {
  14.    ios_base::sync_with_stdio(0);
  15.    cin.tie(0);cout.tie(0);
  16.  
  17.  
  18.  
  19.    ll n,m,i,j,k,l=INT_MIN;
  20.  
  21.  
  22.    cin>>n;
  23.  
  24.    ll a[n+4][n+4];
  25.  
  26.    for(i=0;i<n;i++)
  27.    {
  28.         for(j=0;j<n;j++)
  29.         {
  30.              cin>>a[i][j];
  31.         }
  32.    }
  33.  
  34.    for(i=0;i<n;i++)
  35.    {
  36.  
  37.         ll sum[n+4]={0};
  38.  
  39.         for(j=i;j<n;j++)
  40.         {
  41.              for(k=0;k<n;k++)
  42.              {
  43.                   sum[k]+=a[j][k];
  44.              }
  45.  
  46.              m=0;
  47.  
  48.              for(k=0;k<n;k++)
  49.              {
  50.                   m+=sum[k];
  51.                   l=max(l,m);
  52.                   if(m<0) m=0;
  53.              }
  54.         }
  55.    }
  56.  
  57.    cout<<l<<nl;
  58.  
  59.    get_lost_idiot;
  60. }
  61.  
RAW Paste Data