#DP #MIS #MIS2D #SubRectangle #UVa #Solved

10074 - Take the Land.cpp

//https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1015
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 15;
const int OO = 1e4;
int dp[105][105];
int n, m;

int main() {
    int x;
    while(cin>>m>>n && m!=0) {
        lp(i, m) {
            lp(j, n) {
                cin>>x;
                if(x) {
                    x = -1*OO;
                } else {
                    x = 1;
                }
                dp[i+1][j+1] = x + dp[i+1][j];
            }
        }
        int sum = 0, best = -1*OO, bestOfBest = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = i; j<=n; j++) {
                sum = 0;
                for(int k = 1; k <= m; k++) {
                    x = dp[k][j] - dp[k][i-1];
                    if(sum < 0)
                        sum = x;
                    else
                        sum +=x;
                    if(sum > best) best = sum;
                }
                if(best > bestOfBest) bestOfBest = best;
            }
        }
        cout << bestOfBest << endl;
    }
    return 0;
}