Cod sursa(job #2017294)

Utilizator LucaSeriSeritan Luca LucaSeri Data 31 august 2017 19:17:31
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int MaxN = 1002;
int pal[MaxN][MaxN], mat[MaxN][MaxN];

void Manacher(int n, int m){
    for(int i = 1; i <= n; ++i){
        int mij = 0;
        for(int j = 1; j <= m; ++j){
            if(j <= mij + pal[i][mij]){
                pal[i][j] = min(mij + pal[i][mij] - j, pal[i][mij-(i-mij)]);
            }
            while(j - pal[i][j] > 1 && j + pal[i][j] < m && mat[i][j+pal[i][j]+1] == mat[i][j-pal[i][j]-1]) ++ pal[i][j];
            if(j + pal[i][j] >= mij + pal[i][mij]){
                mij = j;
            }
        }
    }
}

int strabunica(vector <int> v){
    int ans = -1;
    stack <int> stiva;
    stiva.push(0);
    int i = 0;
    while(i < v.size()){
        while(v[i] < v[stiva.top()] && stiva.size() > 1){
            int vf = v[stiva.top()];
            stiva.pop();
            ans = max(ans, vf*(i-stiva.top()-1));
        }
        stiva.push(i);
        ++i;
    }

    return ans;
}

int main(){
    int n, m;
    f >> n >> m;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            f >> mat[i][j];
        }
    }

    Manacher(n, m);
    int ans = -1;
    for(int i = 1; i <= m; ++i){
        vector <int> v;
        v.push_back(0);
        for(int j = 1; j <= n; ++j){
            v.push_back(2*pal[j][i]+1);
        }
        v.push_back(0);
        ans = max(ans,strabunica(v));
    }

    g << ans;
    return 0;
}