Cod sursa(job #2538386)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 4 februarie 2020 18:22:06
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 1005;
int v[NMAX][NMAX];
int p[NMAX][NMAX];
int stiva[NMAX];
int st[NMAX];
int dr[NMAX];

int main() {
    int n, m;
    freopen("dreptpal.in", "r", stdin);
    freopen("dreptpal.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d", &v[i][j]);
        }
    }
    for(int i = 1; i <= n; i++) {
        int x = 0, y = 0;
        v[i][0] = -1;
        v[i][m + 1] = -2;
        for(int j = 1; j <= m; j++) {
            if(y < j) {
                p[i][j] = 1;
            }
            else {
                p[i][j] = min(y - j + 1, p[i][x + y - j]);
            }
            while(v[i][j + p[i][j] - 1] == v[i][j - p[i][j] + 1]) {
                p[i][j]++;
            }
            p[i][j]--;
            if(y < j + p[i][j] - 1) {
                y = j + p[i][j] - 1;
                x = j - p[i][j] + 1;
            }
        }
        for(int j = 1; j <= m; j++) {
            p[i][j] = 2 * p[i][j] - 1;
        }
    }
    int sol = 0;
    for(int j = 3; j <= m; j++) {
        for(int i = 1; i <= n; i++) {
            st[i] = dr[i] = 0;
        }
        int top = 0;
        for(int i = 1; i <= n; i++) {
            while(top > 0 && p[stiva[top]][j] > p[i][j]) {
                dr[stiva[top]] = i - 1;
                top--;
            }
            stiva[++top] = i;
        }
        while(top > 0) {
            dr[stiva[top]] = n;
            top--;
        }
        for(int i = n; i > 0; i--) {
            while(top > 0 && p[stiva[top]][j] > p[i][j]) {
                st[stiva[top]] = i + 1;
                top--;
            }
            stiva[++top] = i;
        }
        while(top > 0) {
            st[stiva[top]] = 1;
            top--;
        }
        for(int i = 1; i <= n; i++) {
            int solc = (dr[i] - st[i] + 1) * p[i][j];
            sol = max(sol, solc);
        }
    }
    printf("%d\n", sol);
    return 0;
}