Cod sursa(job #792023)

Utilizator deneoAdrian Craciun deneo Data 26 septembrie 2012 11:43:58
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;

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

#define MAXN 1100

int n, m;
int sus[MAXN], jos[MAXN], st[MAXN], a[MAXN][MAXN], b[MAXN][MAXN];

int main() {
    int i, j, best, leWildSum = 0;
    fin >> n >> m;
    for (i = 1; i <= n; ++i) 
        for (j = 1; j <= m; ++j)
            fin >> a[i][j];
    
    for (i = 1; i <= n; ++i) 
        for (j = 1, best = 0; j <= m; ++j) {
            if (best + b[i][best] > b[i][j]) 
                b[i][j] = min(best + b[i][best] - j, b[i][2 * best - j]);
            while (j - b[i][j] > 0 && j + b[i][j] <= m && a[i][j - b[i][j]] == a[i][j + b[i][j]])
                ++b[i][j];
            if (j + b[i][j] > best + b[i][best])
                best = j;
        }

    for (i = 1; i <= n; ++i) 
        for (j = 1; j <= m; ++j)
            b[i][j] = b[i][j] * 2 - 1;
     
    for (i = 1; i <= m; ++i) {
        st[0] = 0;
        cerr << "\n";
        for (j = 1; j <= n; ++j) {
            while (st[0] && b[j][i] <= b[st[st[0]]][i])        
                --st[0];
            if (st[0] == 0)
                sus[j] = j;
            else
                sus[j] = j - st[st[0]];
            st[++st[0]] = j;
        }
        st[0] = 0;
        for (j = n; j >= 1; --j) {
            while (st[0] && b[j][i] <= b[st[st[0]]][i])
                --st[0];
            if (st[0] == 0)
                jos[j] = n - j + 1;
            else
                jos[j] = st[st[0]] - j;
            st[++st[0]] = j;
        }
        for (j = 1; j <= n; ++j) 
            leWildSum = max(leWildSum, (sus[j] + jos[j] - 1) * b[j][i]);
    }
    fout << leWildSum << "\n";
    return 0;
}