Cod sursa(job #2663482)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 26 octombrie 2020 15:44:41
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
//
//  main.cpp
//  dreptpal
//
//  Created by she on 26/10/2020.
//  Copyright © 2020 Eusebiu Rares. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
 
std::ifstream in("dreptpal.in") ;
std::ofstream out("dreptpal.out") ;
 
const int MAXN = (1e3) + 1 ;
int pal[MAXN][MAXN], mat[MAXN][MAXN] ;
 
static void GetHeight(int i, int j, int m, int &mij) {
	if(j <= mij + pal[i][mij]){
		pal[i][j] = std::min(mij + pal[i][mij] - j, pal[i][mij - (j - 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 ;
	}
}

void Manacher(int n, int m){
    for(int i = 1 ; i <= n ; ++ i){
        int mij = 0 ;
        for(int j = 1 ; j <= m ; ++ j){
					GetHeight(i, j, m, mij);
        }
    }
}
 
static void addHeight(int &ans, int i, std::stack<int> &stiva, std::vector<int> &v) {
	int vf = v[stiva.top()] ;
	stiva.pop() ;
	ans = std::max(ans, vf * (i-stiva.top() - 1));
}

int skyline(std::vector <int> v){
    int ans = -1 ;
    std::stack <int> stiva ;
    stiva.push(0) ;
    int i = 0 ;
    while(i < v.size()){
        while(v[i] < v[stiva.top()] && stiva.size() > 1){
					addHeight(ans, i, stiva, v) ;
        }
        stiva.push(i) ;
        ++ i ;
    }
 
    return ans ;
}
 
int main(){
    int n, m ;
    in >> n >> m ;
    for(int i = 1 ; i <= n ; ++ i){
        for(int j = 1 ; j <= m ; ++ j){
            in >> mat[i][j] ;
        }
    }
 
    Manacher(n, m) ;
    int ans = -1 ;
    for(int i = 1 ; i <= m ; ++i){
        std::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 = std::max(ans,skyline(v)) ;
    }
 
    out << ans ;
    return 0 ;
}