Cod sursa(job #2586299)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 20 martie 2020 13:39:48
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>

#define NMAX 1005
using namespace std;

ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");

int mat[NMAX][NMAX], n, m, v[NMAX], pz[NMAX][NMAX], st[NMAX][2], poz = 0;

void manacher(int *mat, int *v){
    v[0] = 1;
    int c = 0, r = 0;
    for(int i = 1; i <= m; ++i){
        int lg = 0;
        if(i <= r)
            lg = min(v[2 * c - i], r - i + 1);
        while(i - lg >= 1 && i + lg <= m && mat[i - lg] == mat[i + lg])
            ++lg;
        if(i + lg - 1 > r){
            r = i + lg - 1;
            c = i;
        }
        v[i] = lg;
    }
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j)
            fin >> mat[i][j];
        manacher(mat[i], pz[i]);
    }

    int arieM = 0;
    for(int j = 1; j <= m; ++j){
        pz[0][j] = -1;
        poz = 0;
        st[poz][0] = n, st[poz][1] = 0;
        for(int i = 1; i <= n + 1; ++i){
            if(pz[i][j] > st[poz][0])
                st[++poz][0] = pz[i][j], st[poz][1] = i;
            else {
                while(poz > 0 && st[poz][0] >= pz[i][j]){
                    arieM = max(arieM, (i - st[poz - 1][1] - 1) * (2 * st[poz][0] - 1));
                    --poz;
                }
                st[++poz][0] = pz[i][j], st[poz][1] = i;
            }
        }
    }
    fout << arieM << '\n';
    return 0;
}