Cod sursa(job #2456673)

Utilizator Briana_NeaguNeagu Briana Briana_Neagu Data 15 septembrie 2019 07:55:12
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("dreptpal.in");
ofstream g("dreptpal.out");

int a[1005][1005];
int z[1005][1005];
int stiva[1005];

void make_pal(int col, int m)
{
    int c = 0, r = 0;
    for (int i = 1; i <= m; ++ i)
    {
        int op = 2 * c - i;
        if (i > r || z[col][op] >= r - i)
        {
            if (i > r)
                r = i;
            int k = r;
            while (k <= m && a[col][k] == a[col][2 * i - k])
                k ++;
            k --;
            z[col][i] = k - i;
            if (k > r)
            {
                r = k;
                c = i;
            }
        }
        else
            z[col][i] = z[col][op];
      //  cout << z[col][i] << " ";
    }
    //cout << '\n';
}
int main()
{
    int n, m;
    f >> n >> m;
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= m; ++ j)
            f >> a[i][j];
        a[i][0] = -1;
        make_pal(i, m);
    }
    int ans = 0;
    for (int i = 2; i < m; ++ i)
    {
        int vf = 1;
        stiva[0] = 0;
        stiva[1] = 0;
        z[n + 1][i] = z[0][i] = -1;
        for (int j = 1; j <= n + 1; ++ j)
        {
            while (vf && z[j][i] <= z[stiva[vf]][i])
            {
                ans = max(ans, (z[stiva[vf]][i] * 2 + 1) * (j - stiva[vf - 1] - 1));
                vf --;
            }
            stiva[++ vf] = j;
        }
    }
    g << ans;
}