Cod sursa(job #1859127)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 27 ianuarie 2017 17:36:57
Problema BMatrix Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 200

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; j++){
            while(last && stack[last].val >= h[i][j])
                last--;
            l[i][j].left = stack[last].pos;
            stack[++last].val = h[i][j];
            stack[last].pos = j;
        }

        last = 0;
        stack[last].pos = m + 1;
        for(int j = m; j >= 1; j--){
            while(last && stack[last].val >= h[i][j])
                last--;
            l[i][j].right = stack[last].pos;
            stack[++last].val = h[i][j];
            stack[last].pos = 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);
    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];
    }

    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            w[i][j] = v[j][i];
    create(w, m, n, maxcl);
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            w[i][j] = v[n - j + 1][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;
}