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

10667 - Largest Block.cpp

//https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1608
#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 a[105][105];
int n, m;

int main() {
    int t, r1, r2, c1, c2, x;
    cin>>t;
    while(t--) {
        cin>>n; cin>>m;
        lp(i, n) lp(j, n) a[i+1][j+1] =  1;

        lp(i, m) {
            cin>>r1>>c1>>r2>>c2;
            for(int i = r1; i <= r2; i++) {
                for(int j = c1; j <= c2; j++) {
                    a[i][j] = (-1*OO);
                }
            }
        }
        lp(i, n) lp(j, n) dp[i+1][j+1] = dp[i+1][j] + a[i+1][j+1];
        int sum = 0, best = 0, bestOfBest = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = i; j <= n; j++) {
                sum = 0;
                for(int k=1;k<=n;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;
}