Cod sursa(job #2670873)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 10 noiembrie 2020 20:17:05
Problema DreptPal Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <bits/stdc++.h>
#define DIM 1010
#define INF 2000000000
using namespace std;

int a[DIM][DIM],p[DIM][DIM*2],v[DIM*2],st[DIM],dr[DIM];
deque <int> d;
int n,m,i,j;

void manacher (int a[], int p[]){
    int i, n = 0;
    v[++n] = INF;
    for (i=1;i<=m;i++){
        v[++n] = a[i];
        v[++n] = INF;
    }

    int Left = 0, Right = 0, c = 0;

    for (i=1;i<=n;i++){
        if (i > Right){

            Left = Right = c = i;
            p[i] = 1;

            while (Left - 1 >= 1 && Right + 1 <= n && v[Left-1] == v[Right+1]){
                p[i]++;
                Left--, Right++;
            }

        } else {
            int mirror = c - (i - c);
            p[i] = min (p[mirror], Right - i + 1);

            int st = i - p[i], dr = i + p[i];
            while (st >= 1 && dr <= n && v[st] == v[dr]){
                st--, dr++;
                p[i]++;
            }

            if (i - p[i] + 1 < Left){
                Left = i - p[i] + 1;
                Right = i + p[i] - 1;
                c = i;
            }}}}

int main (){

    ifstream cin ("dreptpal.in");
    ofstream cout ("dreptpal.out");

    cin>>n>>m;
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++)
            cin>>a[i][j];

        manacher(a[i],p[i]);
    }

    int sol = 0;
    for (j=1;j<=m;j++){

        for (i=1;i<=n;i++)
            v[i] = p[i][2*j] - 1;

        d.clear();
        for (i=1;i<=n;i++){
            while (!d.empty() && v[i] <= v[d.back()])
                d.pop_back();

            if (d.empty())
                st[i] = 1;
            else st[i] = d.back() + 1;

            d.push_back(i);
        }

        d.clear();
        for (i=n;i;i--){
            while (!d.empty() && v[i] <= v[d.back()])
                d.pop_back();

            if (d.empty())
                dr[i] = n;
            else dr[i] = d.back() - 1;

            d.push_back(i);
        }

        for (i=1;i<=n;i++)
            sol = max (sol,(dr[i] - st[i] + 1)*v[i] );

    }

    cout<<sol;




    return 0;
}