Cod sursa(job #919031)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 19 martie 2013 12:33:42
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 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();
}