Cod sursa(job #868025)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 30 ianuarie 2013 16:20:10
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <stack>

#define MAX 1005

using namespace std;

int N, M, ans;
int D[MAX], U[MAX];
int V[MAX][MAX], dp[MAX][MAX];

int main()
{
    ifstream in("dreptpal.in"); in>>N>>M;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            in>>V[i][j];
    for(int i = 1; i <= N; i++)
    {
        int C = 0;
        for(int j = 1; j <= M; j++)
        {
            dp[i][j] = max(1, min(dp[i][2 * C - j], C + dp[i][C] - j));
            int L = j - dp[i][j], R = j + dp[i][j];
            while(L && R <= M && V[i][L] == V[i][R]) L--, R++, dp[i][j]++;
            dp[i][j]--;
            if(j + dp[i][j] > C + dp[i][C])
                C = j;
        }
        for(int j = 1; j <= M; j++) dp[i][j] = dp[i][j] * 2 + 1;
    }
    for(int j = 1; j <= M; j++)
    {
        stack<int> S;
        S.push(0);
        for(int i = 1; i <= N; i++)
        {
            while(!S.empty() && dp[i][j] <= dp[S.top()][j]) S.pop();
            U[i] = S.top() + 1;
            S.push(i);
        }
        while(!S.empty()) S.pop();
        S.push(N + 1);
        for(int i = N; i; i--)
        {
            while(!S.empty() && dp[i][j] <= dp[S.top()][j]) S.pop();
            D[i] = S.top() - 1;
            S.push(i);
        }
        for(int i = 1; i <= N; i++) ans = max(ans, dp[i][j] * (D[i] - U[i] + 1));
    }
    ofstream out("dreptpal.out"); out<<ans<<"\n"; out.close();
}