UVa 10074 – Take the land! [solved]

Posted on November 15, 2017 by Mobarak Hosen Shakil — Leave a comment

/******************************************
          Mobarak Hosen Shakil
        ICE, Islamic University
     ID: mhiceiuk(all), 29698(LOJ)
   E-mail: mhiceiuk @ (Gmail/Yahoo/FB)
 Blog: https://iuconvergent.wordpress.com
*******************************************/

#include<bits/stdc++.h>
using namespace std;

#define SM -1e5

int main()
{
    int n, m;
    int maxsum=0, csum=0;
    while(scanf("%d%d", &n, &m) && n!=0)
    {
        int mat[n+5][m+5], temp[n+5];

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                scanf("%d", &mat[i][j]);

                if(mat[i][j]==1)
                    mat[i][j]=-109995;
                else mat[i][j]=1;

            }
        }
        int sum, csum, msum;
        sum=csum=msum=0;
        for(int k=0; k<m; k++)
        {
            memset(temp, 0, sizeof(temp));
            for(int j=k; j<m; j++)
            {
                for(int i=0; i<n; i++)
                    temp[i]+=mat[i][j];

                sum=csum=0;
                for(int i=0; i<n; i++) {
                    sum+=temp[i];
                    csum=max(sum, csum);
                    sum=max(sum, 0);
                }
                msum=max(csum, msum);
            }
        }
        printf("%d\n", msum);
    }
    return 0;
}