Cod sursa(job #1819149)

Utilizator Coroian_DavidCoroian David Coroian_David Data 30 noiembrie 2016 11:50:19
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.24 kb
#include <cstdio>

using namespace std;

FILE *f, *g;

int n, m;

int k;

int rez;

int stk[201], dr;

int h[201];

bool a[201][201];

int left[201], right[201];

int l1_1[201][201];
int l1_2[201][201];
int l2_1[201][201];
int l2_2[201][201];

int dr_up[201];
int dr_dn[201];
int dr_lf[201];
int dr_rg[201];

inline int mxa(int a, int b)
{
    return (a > b ? a : b);
}

inline int mna(int a, int b)
{
    return (a < b ? a : b);
}

void readFile()
{
    f = fopen("bmatrix.in", "r");

    fscanf(f, "%d%d\n", &n, &m);

    int i, j;

    char c;

    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= m; j ++)
            fscanf(f, "%c", &c), a[i][j] = (c - '0');

        fscanf(f, "%c", &c);
    }
}

int skyline(int n, int m, int v[])
{
    int i, j, mx = 0;

    for(i = 1; i <= m; i ++)
        h[i] = /*mna(*/v[i]/*, n)*/;

    dr = 0;

    stk[dr] = 0;

    for(j = 1; j <= m; j ++)
    {
       // printf("*%d ", h[j]);

        while(dr != 0 && h[j] <= h[stk[dr]])
            dr --;

        stk[++ dr] = j;

        left[j] = stk[dr - 1];
    }

   // printf("\n");

    dr = 0;

    stk[dr] = m + 1;

    for(j = m; j >= 1; j --)
    {
        while(dr != 0 && h[j] <= h[stk[dr]])
            dr --;

        stk[++ dr] = j;

        right[j] = stk[dr - 1];
    }

    for(j = 1; j <= m; j ++)
    {
      //  printf("%d %d %d\n", h[j], right[j], left[j]);

        mx = mxa(mx, h[j] * (right[j] - 1 - left[j]));

    }
    return mx;
}

void elements0()
{
    int i, j;

    /// Precalculam matricile l1_1, l2_1, l1_2, l2_2
    /// l1_1[i][j] = nr. de elemente '0' deasupra lui (i, j)
    /// l2_1[j][i] = nr. de elemente '0' in stanga lui (i, j)
    /// l1_2[i][j] = nr. de elemente '0' sub (i, j)
    /// l2_2[j][i] = nr. de elemente '0' in dreapta lui (i, j)

    for (i = 1; i <= n; i ++)
    {
        for (j = 1; j <= m; j ++)
        {
            l1_1[i][j] = (a[i][j] == 0 ) * (l1_1[i - 1][j] + 1);
            l2_1[j][i] = (a[i][j] == 0 ) * (l2_1[j - 1][i] + 1);
        }
    }

    for (i = n; i >= 1; i --)
    {
        for (j = m; j >= 1; j --)
        {
            l1_2[i][j] = (a[i][j] == 0) * (l1_2[i + 1][j] + 1);
            l2_2[j][i] = (a[i][j] == 0) * (l2_2[j + 1][i] + 1);
        }
    }
}

void printElements0()
{
    int i, j;

    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= m; j ++)
            printf("%d ", l1_1[i][j]);

        printf("\n");
    }

    printf("\n");

    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= m; j ++)
            printf("%d ", l1_2[i][j]);

        printf("\n");
    }

    printf("\n");

    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= m; j ++)
            printf("%d ", l2_1[j][i]);

        printf("\n");
    }

    printf("\n");

    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= m; j ++)
            printf("%d ", l2_2[j][i]);

        printf("\n");
    }
}

void maxArie()
{
    int i, j;

    /// Precalculam matricile dr
    /// dr_...[i] = aria maxima a unui dreptunghi [deasupra/sub/in stanga/in dreapta] [liniei/coloanei] i (inclusiv i)

    for (i = 1; i <= n; i ++)
        dr_up[i] = mxa(dr_up[i - 1], skyline(i, m, l1_1[i]));

    for (i = 1; i <= m; i ++)
        dr_lf[i] = mxa(dr_lf[i - 1], skyline(i, n, l2_1[i]));

    for (i = n; i >= 1; i --)
        dr_dn[i] = mxa(dr_dn[i + 1], skyline(n - i + 1, m, l1_2[i]));

    for (i = m; i >= 1; i --)
        dr_rg[i] = mxa(dr_rg[i + 1], skyline(m - i + 1, n, l2_2[i]));
}

void solve()
{
    int i, j;

    elements0();

   // printElements0();

    maxArie();

   /* for(i = 1; i <= n; i ++)
    {
        printf("%d %d\n", dr_up[i], dr_dn[i]);
    }

    printf("\n");

    for(i = 1; i <= m; i ++)
    {
        printf("%d %d\n", dr_lf[i], dr_rg[i]);
    }*/

    for ( i = 1; i <= n; i ++ )
        rez = mxa( rez, dr_up[i] + dr_dn[i + 1] );
    for ( i = 1; i <= m; i ++ )
        rez = mxa( rez, dr_lf[i] + dr_rg[i + 1] );
}


void printFile()
{
    g = fopen("bmatrix.out", "w");

    fprintf(g, "%d\n", rez);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}