Pagini recente » Cod sursa (job #277443) | Cod sursa (job #228160) | Cod sursa (job #2241993) | Cod sursa (job #2529254) | Cod sursa (job #2663482)
//
// 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 ;
}