Cod sursa(job #1100785)

Utilizator Ionut228Ionut Calofir Ionut228 Data 7 februarie 2014 14:41:41
Problema DreptPal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <cstdlib>

using namespace std;

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

int N, M;
int maxarea;
int A[1001][2002], P[1001][2002];
int lf[1001], rg[1001];
stack<int> ST;

void pscpld()
{
    for (int i = 1; i <= N; ++i)
    {
        int best = 0;
        for (int j = 1; j <= M; ++j)
        {
            if (best + P[i][best] >= j)
                P[i][j] = min(best + P[i][best] - j, P[i][2 * best - j]);
            while (j - P[i][j] - 1 > 0 && j + P[i][j] + 1 <= M && A[i][j - P[i][j] - 1] == A[i][j + P[i][j] + 1])
                ++P[i][j];
            if (j + P[i][j] >= best + P[i][best])
                best = j;
        }
    }
}

int main()
{
    fin >> N >> M;
    M = 2 * M + 1;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
        {
            if (j % 2 == 1) A[i][j] = -1;
            else            fin >> A[i][j];
        }

    pscpld();

    for (int j = 6; j <= M; j += 2)
    {
        while (!ST.empty())
            ST.pop();
        for (int i = 1; i <= N; ++i)
        {
            while (!ST.empty() && P[i][j] <= P[ST.top()][j])
                ST.pop();
            if (ST.empty()) lf[i] = i;
            else            lf[i] = i - ST.top();
            ST.push(i);
        }

        while (!ST.empty())
            ST.pop();
        for (int i = N; i >= 1; --i)
        {
            while (!ST.empty() && P[i][j] <= P[ST.top()][j])
                ST.pop();
            if (ST.empty()) rg[i] = i;
            else            rg[i] = ST.top() - i;
            ST.push(i);
        }

        for (int i = 1; i <= N; ++i)
            maxarea = max(maxarea, P[i][j] * (abs(lf[i] - rg[i]) + 1));
    }

    fout << maxarea << '\n';

    fin.close();
    fout.close();
    return 0;
}