UVa : 836 (Largest Submatrix)



// http://uva.onlinejudge.org/external/8/836.html
// Runtime : 0.008s
// Tag : Ad-Hoc, Dp


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

int main ()
{
    //freopen ("input", "r", stdin);
    int testCase;
    scanf ("%d", &testCase);
    bool space = false;
    getchar ();

    char input [25 + 3] [25 + 3];
    gets (input [0]);

    while ( testCase-- ) {
        
        int index = 0;

        while ( gets (input [index]) && strlen (input [index]) ) index++;

        int a [25 + 3] [25 + 3];

        for ( int i = 0; i < index; i++ )
            for ( int j = 0; j < index; j++ )
                a [i] [j] = input [i] [j] == '1' ? 1 : 0;
        /*
        for ( int i = 0; i < index; i++ ) {
            for ( int j = 0; j < index; j++ ) printf ("%d", a [i] [j]);
            printf ("\n");
        }
        */

        for ( int i = 1; i < index; i++ )
            for ( int j = 0; j < index; j++ )
                a [i] [j] = a [i] [j] == 1 ? a [i - 1] [j] + 1 : 0;


        int maxi = INT_MIN;

        for ( int i = 0; i < index; i++ ) {
            for ( int j = 0; j < index; j++ ) {
                int cnt = 1;
                for ( int k = j - 1; k >= 0 && a [i] [k] >= a [i] [j]; k-- ) cnt++;
                for ( int k = j + 1; k < index && a [i] [k] >= a [i] [j]; k++ ) cnt++;
                cnt *= a [i] [j];
                if ( maxi < cnt ) maxi = cnt;
            }
        }

        if ( space ) printf ("\n"); space = true;
        printf ("%d\n", maxi);
    }

	return 0;
}

// @END_OF_SOURCE_CODE

2 thoughts on “UVa : 836 (Largest Submatrix)

  1. Please explain this portion:

    for ( int i = 0; i < index; i++ ) {
    for ( int j = 0; j = 0 && a [i] [k] >= a [i] [j]; k-- ) cnt++;
    for ( int k = j + 1; k = a [i] [j]; k++ ) cnt++;
    cnt *= a [i] [j];
    if ( maxi < cnt ) maxi = cnt;
    }
    }

  2. Please explain this portion:

    for ( int i = 0; i < index; i++ ) {
    for ( int j = 0; j = 0 && a [i] [k] >= a [i] [j]; k– ) cnt++;
    for ( int k = j + 1; k = a [i] [j]; k++ ) cnt++;
    cnt *= a [i] [j];
    if ( maxi < cnt ) maxi = cnt;
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s