Cod sursa(job #3197967)

Utilizator stefanrotaruRotaru Stefan-Florin stefanrotaru Data 27 ianuarie 2024 19:35:01
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>

using namespace std;

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

int n, m, a[1005], st[1005], dr[1005], s[1005], p[1005][1005];

void Manacher(int i)
{
    a[0] = -1;
    a[m + 1] = -2;

    int r = 0, c = 0;

    for (int j = 1; j <= m; ++j) {
        f >> a[j];
    }

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

        if (j < r) {
            cur = min(r - j, p[i][2 * c - j]);
        }

        while (a[j + cur + 1] == a[j - cur - 1]) {
            cur++;
        }

        if (j + cur > r) {
            r = j + cur;
            c = j;
        }

        p[i][j] = cur;
    }
}

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

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

    int sol = 0;

    for (int j = 1; j <= m; ++j) {
        int k = 0;
        s[k] = 0;

        for (int i = 1; i <= n; ++i) {
            while (k && p[i][j] <= p[s[k]][j]) {
                k--;
            }

            st[i] = s[k] + 1;
            s[++k] = i;
        }

        k = 0;
        s[k] = n + 1;

        for (int i = n; i >= 1; --i) {
            while (k && p[i][j] <= p[s[k]][j]) {
                k--;
            }

            dr[i] = s[k] - 1;
            s[++k] = i;
        }

        for (int i = 1; i <= n; ++i) {
            sol = max(sol, (dr[i] - st[i] + 1) * (p[i][j] * 2 + 1));
        }
    }

    g << sol;

    return 0;
}