Cod sursa(job #1859273)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 27 ianuarie 2017 18:15:06
Problema BMatrix Scor 92
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.h>

#define MAXN 300

int v[1 + MAXN][1 + MAXN];
int w[1 + MAXN][1 + MAXN];
int h[1 + MAXN][1 + MAXN];
int maxs[1 + MAXN][1 + MAXN];
int maxlu[1 + MAXN];
int maxld[1 + MAXN];
int maxcl[1 + MAXN];
int maxcr[1 + MAXN];
struct limit{
    int left, right;
}l[1 + MAXN][1 + MAXN];

struct st{
    int val;
    int pos;
}stack[1 + MAXN];
int last;

inline void create(int v[][1 + MAXN], int n, int m, int maxv[]){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            h[i][j] = v[i][j] * (h[i - 1][j] + v[i][j]);
    for(int i = 1; i <= n; i++){
        maxv[i] = 0;
        last = 0;
        stack[last].pos = 0;
        for(int j = 1; j <= m + 1; j++){
            while(last && stack[last].val > h[i][j]){
                l[i][stack[last].pos].right = j;
                last--;
            }
            stack[++last].val = h[i][j];
            stack[last].pos = j;
        }

        last = 0;
        stack[last].pos = m + 1;
        for(int j = m; j >= 0; j--){
            while(last && stack[last].val > h[i][j]){
                l[i][stack[last].pos].left = j;
                last--;
            }
            stack[++last].val = h[i][j];
            stack[last].pos = j;
        }
        for(int j = 1; j <= m; j++){
            maxs[i][j] = v[i][j] * h[i][j] * (l[i][j].right - l[i][j].left - 1);
            if(maxs[i][j] > maxv[i])
                maxv[i] = maxs[i][j];
        }

        if(maxv[i - 1] > maxv[i])
            maxv[i] = maxv[i - 1];
    }
}

int main(){
    FILE*fi,*fo;
    fi=fopen("bmatrix.in","r");
    fo=fopen("bmatrix.out","w");

    int n, m;
    fscanf(fi,"%d%d", &n, &m);
    fgetc(fi);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            v[i][j] = fgetc(fi);
            v[i][j] -= '0';
            v[i][j] = 1 - v[i][j];
        }
        fgetc(fi);
    }

    create(v, n, m, maxlu);

    memset(w, 0, sizeof(w));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            w[i][j] = v[n - i + 1][j];
    create(w, n, m, maxld);

    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(maxlu[i] + maxld[n - i] > ans)
            ans = maxlu[i] + maxld[n - i];
    }

    memset(w, 0, sizeof(w));
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            w[i][n - j + 1] = v[j][i];
    create(w, m, n, maxcl);

    memset(w, 0, sizeof(w));
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            w[m - i + 1][j] = v[j][i];
    create(w, m, n, maxcr);

    for(int i = 1; i <= m; i++){
        if(maxcl[i] + maxcr[m - i] > ans)
            ans = maxcl[i] + maxcr[m - i];
    }

    fprintf(fo,"%d", ans);
    fclose(fi);
    fclose(fo);
    return 0;
}