Cod sursa(job #2023384)

Utilizator Alex18maiAlex Enache Alex18mai Data 18 septembrie 2017 21:01:53
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <stack>

using namespace std;

ifstream cin("dreptpal.in");
ofstream cout("dreptpal.out");

int n, m;
int mat[1010][1010];
int aux[2020];
int pali[2020][2020];
stack <int> S;

void citire(){
    cin>>n>>m;
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            cin>>mat[i][j];
            //cout<<mat[i][j]<<" ";
        }
        //cout<<'\n';
    }

}

void make_pali(int line){
    aux[0] = -2;
    int pos = 1;
    for (int i=1; i<=m; i++){
        aux[pos++] = -1;
        aux[pos++] = mat[line][i];
    }
    aux [pos++] = -1;
    aux [pos] = -3;
    /*cout<<"AUX de "<<line<<" :"<<'\n';
    for (int i=0; i<=pos; i++){
        cout<<aux[i]<<" ";
    }
    cout<<'\n';*/
    pos--;
    int R = 0;
    int C = 0;
    for (int i=1; i<=pos; i++){
        int opus = C * 2 - i;
        if (R > i){
            pali[line][i] = min(pali[line][opus] , R - i);
        }
        while (aux[i + pali[line][i] + 1] == aux[i - pali[line][i] - 1]){
            pali[line][i]++;
        }
        if (i + pali[line][i] > R){
            R = i + pali[line][i];
            C = i;
        }
    }
}

void test(){
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m * 2 + 2; j++){
            cout<<pali[i][j]<<" ";
        }
        cout<<'\n';
    }
}

void strabunica(int col, int &MAX){
    S.push(0);
    pali[n+1][col] = 0;
    for (int i=1; i<=n + 1; i++){
        int val = pali[i][col];
        while (!S.empty() && pali[S.top()][col] > val){
            int nr =  pali[S.top()][col];
            S.pop();
            MAX = max(MAX , nr * (i - S.top() - 1) );
        }
        S.push(i);
    }
}

void solve(int &MAX){
    int pm = m*2 + 2;
    for (int i=1; i<=n; i++){
        make_pali(i);
    }
    for (int i=1; i<=pm; i++){
        strabunica(i , MAX);
    }
    //test();
}


int main() {

    citire();
    int MAX = 0;
    solve(MAX);
    cout<<MAX;

    return 0;
}