Cod sursa(job #2786040)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 20 octombrie 2021 08:56:05
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");

int n, m, ans, v[1005][1005], manacher[1005][1005];
int aux[1005], st[1005], dr[1005], stiva[1005];

void compute_manacher(int ind);

void solve(int ind);

int main() {
    fin >> n >> m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            fin >> v[i][j];
        }
    }

    for (int i=1;i<=n;i++){
        compute_manacher(i);
    }

    for (int i=1;i<=m;i++){
        solve(i);
    }

    fout << ans << '\n';

    return 0;
}

void solve(int ind) {
    for (int i=1;i<=n;i++)
        aux[i] = manacher[i][ind], st[i] = dr[i] = 0;

    int nr;

    for (int i=1;i<=n;i++){
        if (i == 1){
            nr = 1;
            stiva[1] = 1;
        }else{
            while(nr && aux[i] < aux[stiva[nr]]){
                dr[stiva[nr]] = i;
                nr --;
            }
            stiva[++nr] = i;
        }
    }

    for (int i=1;i<=nr;i++)
        dr[stiva[i]] = n + 1;

    for (int i=n;i>=1;i--){
        if (i == n){
            nr = 1;
            stiva[1] = n;
        }else{
            while(nr && aux[i] < aux[stiva[nr]]){
                st[stiva[nr]] = i;
                nr --;
            }
            stiva[++nr] = i;
        }
    }

    for (int i=1;i<=n;i++){
        int latime = dr[i] - st[i] - 1;
        int lungime = aux[i] * 2 - 1;

        ans = max(ans, latime * lungime);
    }
}

void compute_manacher(int ind) {

    int l = 0, r = 0;
    for (int i=1;i<=m;i++){
        int k;
        if (i > r)
            k = 1;
        else
            k = min(manacher[ind][l+r-i], r-i+1);

        while(i-k>=1 && i+k<=m && v[ind][i-k] == v[ind][i+k]){
            k ++;
        }

        manacher[ind][i] = k;
        k --;

        if (i + k > r){
            l = i - k;
            r = i + k;
        }
    }

}